# What's the best software for primality tests of huge numbers? (check if an integer is prime or not)

I just read an article about huge prime numbers (some with more than 10millions digits!) that are discovered using software that check if an integer is prime or not (primality test sofwares).

What is the best software that can handle extremely huge numbers like 2^200000000-1 ? I know that most famous is Prime95 (which is also used for pc benchmarking) because it is often updated, but it only works for Marsenne prime numbers (prime numbers in the form of (2^x)-1 like the one i suggested before). With Prime95 you can only test different exponents, and hopefully within some days you get the results (consider that 2^200000000-1 is a 60million++ digits number!)

Is there something like Prime95 for every integer and not just for Marsenne's? Obviously I could write a program myself but it would be useful only for small numbers. To verify primality of huge numbers you need a professional software that correctly uses CPU multithreading and thing like that.

Anyone in the field that can give me any tips? Thanks! PS. sorry for my bad english

• Note: it is very easy to see that the example you have given is not prime, because the exponent you have used is obviously not prime. $2^{pq}-1$ is divisible by $2^p-1$ – Mark Bennet Jul 12 '14 at 6:44
• I searched for AKS and found sourceforge.net/projects/aksprimality. Now AKS is probably not the best algorithm for such small primes, but since they mentioned "record execution time" it might worth a try. – Gina Jul 12 '14 at 6:50
• Support of multithreading will not be the tiebreaker between algorithms as that speed up at most by a constant factor – Hagen von Eitzen Jul 12 '14 at 7:04
• @HagenvonEitzen: well, if your primes took 100 years to check, and you are running a 10000 cores machine, it could reduce down a calculation that would be longer than your life to just a few days. Since this is a practical question more than theoretical, I think the constant factors can be important. Which is why I said AKS is probably not the best algorithm for such small primes. – Gina Jul 12 '14 at 7:11

No, it's not currently possible to prove primality of arbitrary numbers of anywhere near that size.

Primo can generate a primality proof for arbitrary numbers. It's current record prime has 23770 decimal digits, a mere drop in the ocean compared to the size of known Mersenne primes. This is probably about as good as it gets.

Other than that, you could instead use probabilistic primality testing; assuming you'd be happy with a minuscule probability of being wrong (a smaller probability than a random error by your computer in a deterministic primality proof).

By the way, if you just want to look for large primes that others aren't looking for, Proth's Theorem and the Lucas-Lehmer-Riesel Test are about as efficient as the Lucas-Lehmer Test (just less popular).

• Also, searching for large primes typically requires running computers at full speed for years at a time, resulting in unnecessary CO$_2$ emissions. I gave up searching for this reason. – Rebecca J. Stones Jul 12 '14 at 7:48
• I assume the CO$_2$ you mention comes from generating the electricity, or is it from some other source? – Frank Hubeny Mar 12 '16 at 13:06

You might want to look at this comparison (mirror).

In short, there are various programs to perform Lucas-Lehmer test (Mersenne numbers), Lucas-Lehmer-Riesel test ($$k \cdot 2^n−1$$), Proth's test ($$k \cdot 2^n+1$$), N-1 Pocklington test ($$k \cdot b^n+1$$) Elliptic Curve Primality Proving (any odd numbers), probable prime tests, etc.

Some of these run on a CPUs, some of them are highly optimized for powerful multicore processors with SIMD instructions, and some are using GPUs (like CUDALucas or clLucas).

But according to the list of largest known primes, the most frequently used programs are actually George Woltman's Prime95 and Jean Penné's LLR.