  Home
News
How ?
Bench

Status
Reserve
Submit
Results
Producers

Math.
Algo.
Stat.
Fun

Credits
Feedback

## Welcome to the Generalized Fermat Prime Search!

During the 17th century, Pierre de Fermat and Marin Mersenne studied two particular forms of numbers, thinking that they could produce a large amount of prime numbers or even to be ever prime. Mersenne communicated a list of the primes of the form 2n-1, for all n < 257. It required many years of labour to produce a correct version of the list, which is close to Mersenne's list. In his correspondence with Frénicle, Fermat expressed his conviction that if n is a power of 2, then 2n+1 is a prime. Fermat knew that 3, 5, 17, 257 and 65537 are primes but later Euler showed that Fermat's conjecture is false by discovering a factor to the next number.

In honour of the inspired pioneers, the numbers of the form 2n-1 are now called the Mersenne numbers and the numbers of the form 2n+1 the Fermat numbers. The search for Mersenne and Fermat primes has been greatly extended since the 17th century. Today, all the Mersenne primes having less than 2,000,000 digits are known and all the Fermat primes up to 2,000,000,000 digits! It was possible because during the 19th century some efficient tests were discovered to check the primality of these numbers. But at the same time, some tests as fast were also found to test check the primality of all the numbers N where the factorization of N-1 or N+1 is known. Then many forms could be used to find the largest known prime but surprisingly the search was almost restricted to the Mersenne numbers. The famous exceptions were (2148+1)/17 (identified in 1951 by A. Ferrier by using hand computing method), 180.(2127-1)2+1 (discovered in 1951 by Miller and Wheeler) and 391581.2216193-1 (found by the "Amdahl 6" in 1989).

From the 50's to the 70's, the size of the largest known prime has grown continuously with the speed of computers but the algorithms used to find them were the same as those used at the end of the 19th century. But in the 80's, the method used to compute the basic operation of the algorithm, the multiplication, changed. By remarking that a multiplication can be evaluated by a convolution, the theory of discrete transforms (that was originally developed for digital signal processing) indicates to us how to compute this operation quickly with some Fast Fourier Transforms. With this method, some primes with more than 10,000 and 100,000 digits were found.

In 1994, R. Crandall and B. Fagin discovered that the Discrete Weighted Transforms could be used to double the speed of the search for Mersenne and Fermat numbers. It was used to find six new Mersenne primes (the largest of them has more than 6,000,000 digits) and to prove the composite character of some Fermat numbers. But the Fermat and Mersenne primes are rare and the chance to find a new prime is small.

In 1998, Y. Gallot remarked that the Discrete Weighted Transform is a polynomial operation and that if the representation of the numbers is not limited to the base 2, then many numbers can be tested at the same speed as a Mersenne number: the Generalized Fermat Numbers which are the numbers of the form bn+1, where n is a power of 2. He implemented the algorithm in 1999 in Proth.exe and since, he has been optimizing. The theoretical hypothesis is now a reality: the search for Generalized Fermat primes is as fast as the search for a Mersenne primes of the same size. With few tens of computers, many primes having more than 100,000 digits were quickly found, the largest of them has more than 800,000 digits. In 2002, P. Carmody together with B. Frey made great strides in a Generalized Fermat Number sieving algorithm. P. Carmody  is organizing a massive sieving effort, with a powerful program written by D. Underbakke, that even speeds up the Generalized Fermat Numbers Search.

Generalized Fermat Numbers are more numerous than Mersenne numbers at equal size and many of them are waiting to be discovered to fill the gaps between the Mersenne primes already found or not yet found. If you are interested in the search for the primes of the 21st century, you are welcome to the Generalized Fermat Prime Search!