In 1997, the "Proth program" Proth.exe was
created by Yves Gallot for the search for large prime
factors of Fermat numbers and implemented the following
theorem:

Proth's Theorem (1878):

Let N = k*2^{n} + 1 with
k < 2^{n}. If there is an
integer a such that
a^{(N1)/2} = 1 (mod
N), then N is prime.
Now, the "Proth program" has been expanded to
cover the primality test of all numbers N of the
form k*b^{n} + 1 or
k*b^{n}  1.
It is designed to allow test of any number of these forms
and the largest of them, which can be tested on modern
computers, have more than 10,000,000 digits! Then in
practice, the difficulty of the test is quickly
multiplying the large numbers involved. Proth is highly
optimized for the test of large numbers (more than 10,000
digits). Discrete Weighted Transform and Fast Fourier
Transform multiplication is used for squaring or
multiplying, plus fast modular operations (using the
special form of N) are also employed for speed
purposes.
Proth.exe has been used to find the most primes (of any
program) on the list of Largest Known Primes. It has also
been used to find most of the largest known nonMersenne
primes.
