Developer(s) | George Woltman |
---|---|
Initial release | 3 January 1996 |
Stable release | 30.19 build 20 [1] / June 2, 2024 |
Preview release | 30.19 build 21 [2] / September 14, 2024 |
Written in | ASM, C |
Operating system | Microsoft Windows, macOS, Linux, FreeBSD |
Type | Mersenne prime finder / system stability tester |
License | Freeware [3] |
Website | mersenne |
Prime95, also distributed as the command-line utility mprime for FreeBSD and Linux, is a freeware application written by George Woltman. It is the official client of the Great Internet Mersenne Prime Search (GIMPS), a volunteer computing project dedicated to searching for Mersenne primes. It is also used in overclocking to test for system stability. [4]
Although most [5] of its source code is available, Prime95 is not free and open-source software because its end-user license agreement [3] states that if the software is used to find a prime qualifying for a bounty offered by the Electronic Frontier Foundation, [6] then that bounty will be claimed and distributed by GIMPS.
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 [7] 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. [8] [9] [10] 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. [11]
To maximize search throughput, most of Prime95 is written in hand-tuned assembly, which makes its system resource usage much greater than most other computer programs. Additionally, due to the high precision requirements of primality testing, the program is very sensitive to computation errors and proactively reports them. These factors make it a commonly used tool among overclockers to check the stability of a particular configuration. [4]
The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use freely available software to search for Mersenne prime numbers.
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form Mn = 2n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If n is a composite number then so is 2n − 1. Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form Mp = 2p − 1 for some prime p.
A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.
In mathematics, a Fermat number, named after Pierre de Fermat (1607–1665), the first known to have studied them, is a positive integer of the form: where n is a non-negative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ....
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.
In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.
In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that n is prime.
George Woltman is the founder of the Great Internet Mersenne Prime Search (GIMPS), a distributed computing project researching Mersenne prime numbers using his software Prime95. He graduated from the Massachusetts Institute of Technology (MIT) with a degree in computer science. He lives in North Carolina. His mathematical libraries created for the GIMPS project are the fastest known for multiplication of large integers, and are used by other distributed computing projects as well, such as Seventeen or Bust.
In mathematics, a double Mersenne number is a Mersenne number of the form
John Lewis Selfridge, was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.
Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.
Ralph Ernest Powers was an American amateur mathematician who worked on prime numbers.
The largest known prime number is 2136,279,841 − 1, a number which has 41,024,320 digits when written in base 10. It was found on October 12, 2024 by a computer volunteered by Luke Durant to the Great Internet Mersenne Prime Search (GIMPS).
In computational number theory, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public-key cryptography, and search of prime factors in large numbers.
In mathematics, the Mersenne conjectures concern the characterization of a kind of prime numbers called Mersenne primes, meaning prime numbers that are a power of two minus one.
In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form N = k ⋅ 2n − 1 with odd k < 2n. The test was developed by Hans Riesel and it is based on the Lucas–Lehmer primality test. It is the fastest deterministic algorithm known for numbers of that form. For numbers of the form N = k ⋅ 2n + 1, either application of Proth's theorem or one of the deterministic proofs described in Brillhart–Lehmer–Selfridge 1975 are used.
In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer. The test uses a partial factorization of to prove that an integer is prime.