Let say I've found a very very very long prime number. I know it's prime but I need to have a proof. Is there any fast way how to check if a number is really prime?

Let say I've found the longest prime number, longer than the longest known and I want to confirm it in very short time (seconds). Is it possible?


closed as not a real question by Dominic Michaelis, J. M. is a poor mathematician, Joe, Alexander Gruber, Paul May 1 '13 at 4:32

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ If you figure a way out let me know haha $\endgroup$ – Benzne_O Apr 22 '13 at 8:29
  • 7
    $\begingroup$ How do you know it's a prime number if you don't have a proof? $\endgroup$ – Joel Reyes Noche Apr 22 '13 at 8:31
  • $\begingroup$ If I knew an answer to this question, I'd probably be holding a Fields medal by now... $\endgroup$ – A.P. Apr 22 '13 at 8:41
  • 1
    $\begingroup$ Ask the NSA or the CIA. If anybody knows, they do. $\endgroup$ – Neal Apr 22 '13 at 13:24
  • 1
    $\begingroup$ The Lucas-Lehmer test on a CPU for a number of this magnitude takes about 6 days using optimized code. That is specific to Mersenne numbers, and for will be at least as fast as a Fermat test, which is the simplest decent compositeness (probable primality) test. So clearly our time scales are way off from what you would like, and we still just have a PSP, not a SPSP and certainly not a proven prime. Without some special form you're practically limited to ~40k digits (ECPP using Primo, a nice workstation/server, and a few months). This is rather small compared to the recent Mersenne primes. $\endgroup$ – DanaJ Aug 24 '17 at 19:21

If the number is of general form, fastest would be one of the modern versions of ECPP. This is several orders of magnitude faster than AKS.

If you can tolerate a tiny probability of error, the Miller-Rabin test works very well here.

If you can tolerate error, but only infinitesimally small, the Frobenius tests can provide much better worst-case error bounds than Miller-Rabin.

If the number is of special form the Lucas test or its variants might be applicable.

  • $\begingroup$ For the purpose of this question -- a large number claimed to be prime, but without any evidence -- I highly recommend Miller-Rabin. A test might take a few months on a good computer if it's close to the maximum known, or longer if it's far beyond. But this is much better than the time it would take for a full proof. $\endgroup$ – Charles Apr 22 '13 at 18:09

I guess the Fastest method known till date is - AKS Primality Test

However it won't be able to find the longest prime number within seconds.

  • 6
    $\begingroup$ This is an extremely slow test, even with Bernstein's modifications. $\endgroup$ – Charles Apr 22 '13 at 13:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.