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.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityWith 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.
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.
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$