Prime95 tests numbers for primality using the
Fermat primality test (referred to internally as PRP, or "probable prime"). For much of its history, it used the
Lucas–Lehmer primality test, but the availability of Lucas–Lehmer assignments was deprecated in April 2021 to increase search throughput. Specifically, to guard against faulty results, every Lucas–Lehmer test had to be performed twice in its entirety, while Fermat tests can be verified in a small fraction of their original run time using a proof generated during the test by Prime95. Current versions of Prime95 remain capable of Lucas–Lehmer testing for the purpose of double-checking existing Lucas–Lehmer results, and for fully verifying "probably prime" Fermat test results (which, unlike "prime" Lucas–Lehmer results, are not conclusive). To reduce the number of full-length primality tests needed, Prime95 first checks numbers for trivial
compositeness by attempting to find a small
factor. As of 2024, test candidates are mainly filtered using
Pollard's p − 1 algorithm.
Trial division is implemented, but Prime95 is rarely used for that work in practice because it can be done much more efficiently using a
GPU, due to the type of arithmetic involved. Finally, the
elliptic-curve factorization method and
Williams's p + 1 algorithm are implemented, but are considered not useful at modern GIMPS testing levels and mostly used in attempts to factor much smaller Mersenne numbers that have already undergone primality testing. GIMPS has discovered 18 new Mersenne primes since its foundation in 1996, the first 17 of which using Prime95. The 18th and most recent, M136279841, was discovered in October 2024 using an
Nvidia GPU, being the first GIMPS discovery to not have used Prime95 and its
CPU computation. 15 of the 17 primes discovered with Prime95 were the
largest known prime number at the time of their respective discoveries, the exceptions being M37156667 and M42643801, which were discovered out of order from the larger M43112609. == gwnum ==