With modern tecnology is it possible to prove the primality of a number of more than 50k digits?
Obviously not a prime for which specific methods for testing primality are known like Mersenne primes.
$\begingroup$
$\endgroup$
3
-
4$\begingroup$ A Google search returned ellipsa.eu/public/primo/primo.html, which as of 2 years ago, in the last update, worked up to 50,000 digits. See also google.com/… $\endgroup$– David Roberts ♦Feb 8 at 8:43
-
4$\begingroup$ "possible", yes, for any number of digits that fits your machine, if you are patient enough. The question is a bit vague - we would expect you have read the literature on primality tests. So why "50k"? What do you know about the question already? $\endgroup$– Chris WuthrichFeb 8 at 9:19
-
1$\begingroup$ @ChrisWuthrich The number 50k might come from the fact that primo currently has (if I understand correctly) a hard-coded limit of 50k digits. $\endgroup$– AurelFeb 8 at 10:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
Yes, it is possible, but it is close to the boundary of what is reasonable. See for instance this software that was recently used by Andreas Enge to prove the primality of $10^{50000}+65859$. It took 100 days of real time and 71 years of CPU time. The certificate can be verified in 4 hours with 128 cores.
-
1$\begingroup$ Can this be done much faster probabilistically, say with probability 1-2^(-100)? Is there a range of digits (maybe 100,000-digits or million-digit numbers?) where rigorous proofs is completely out of reach but probabilistic proofs can be done fast on usual PC? $\endgroup$ Feb 8 at 15:26
-
6$\begingroup$ @BogdanGrechuk Yes, there are much faster probabilistic algorithms, for instance the Rabin-Miller test, to name only one. The whole difficulty here is to obtain a proof (and even an efficiently verifiable certificate). $\endgroup$– AurelFeb 8 at 15:46
-
1$\begingroup$ @BogdanGrechuk For instance the Pari/GP function
ispseudoprimeimplements a version of the BPSW primality test, for which infinitely many pseudoprimes (composites that pass the test) are conjectured to exist but none is known. On the above example, it terminates in 15 minutes on a single core. $\endgroup$– AurelFeb 8 at 19:44 -
$\begingroup$ The record on 50001 digits (from June) was beaten in September by a 57125-digit prime. Also proved with Enge's CM software. See PrimePages Top Twenty: Elliptic Curve Primality Proof. $\endgroup$ Feb 8 at 22:50
-
$\begingroup$ If you take "Rabin-Miller test with 100 rounds" then it is most likely that there are an infinite number of pseudoprimes exist, but none will ever be known. Over three quarters would be identified as composite if. you ran 101 rounds of the test. $\endgroup$ Feb 9 at 11:02