12
$\begingroup$

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.

$\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
    Commented Feb 8, 2023 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$ Commented Feb 8, 2023 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$
    – Aurel
    Commented Feb 8, 2023 at 10:31

1 Answer 1

23
$\begingroup$

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.

$\endgroup$
7
  • 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$ Commented Feb 8, 2023 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$
    – Aurel
    Commented Feb 8, 2023 at 15:46
  • 1
    $\begingroup$ @BogdanGrechuk For instance the Pari/GP function ispseudoprime implements 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$
    – Aurel
    Commented Feb 8, 2023 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$ Commented Feb 8, 2023 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$
    – gnasher729
    Commented Feb 9, 2023 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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