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).
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!
