The "Proth" program

and

the search for prime numbers

Yves Gallot

*Or, pour comprendre une théorie, il ne
suffit pas de constater que le chemin que l'on a suivi n'est pas
coupé par un obstacle, il faut se rendre compte des raisons qui
l'ont fait choisir. Pourra-t-on donc jamais dire qu'on comprend
une théorie si on veut lui donner d'emblée sa forme définitive,
celle que la logique impeccable lui impose, sans qu'il ne reste
aucune trace des tâtonnements qui y ont conduit ? Non, on ne la
comprendra pas réellement, on ne pourra même la retenir, ou on
ne la retiendra qu'à force de l'apprendre par cœur.*

Henri Poincaré, Œuvres, 1899.

*To understand a theory, it is not sufficient
to notice that the way we followed is not blocked by an obstacle,
we should be aware of the reasons for which it was chosen. Will we
ever be able to say that we understand a theory if we want to give
to it straightaway its final form, that impeccable logic imposes on
it ? Which ideas were tried out and discarded, which ideas were
tried out and retained ? If we don't know these things we will not
really understand it, we will even not be able to remember it; at
best we will only remember it by learning it off
by heart.*

CONTENTS

- History of the Proth program
- Primality tests
- Fast evaluation of tests
- Actual searches for prime numbers
- Search of tomorrow

History of the Proth program

- Proth.exe was created in 1997.
- Originally to extend the search for large
factors of Fermat numbers (
*k*.2^{n}+ 1). - Several implementations were evaluated.
- In 1997, Carlos Rivera discovered 9183.2
^{262112 }+ 1 (largest known "non-Mersenne" prime).

History of the Proth program

- In 1998, largest known "Sophie
Germain" prime: 92305.2
^{16998 }+ 1 (Chip Kerchner). - Program was extended to also cover the
form
*k*.2^{n}- 1. - Largest known twin primes 835335.2
^{39014}+/-1 (Ray Ballinger) and "Sophie Germain" prime: 72021.2^{23630}-1.

History of the Proth program

- In 1998, major "theoretical"
improvement: ability to test
*k*.*b*^{n}+ 1, for small b, in about the same time as a number*k*.2^{n}+ 1 of the same size.

History of the Proth program

- Transform of Proth.exe was totally rewritten in 1999: testable numbers extended to 5,000,000 digits.
- Efficient test of Generalised Fermat
Numbers (
*b*^{2n}+ 1) was implemented: test of a GFN is up to 2 times faster than a number*k*.2^{n}+ 1 of the same size.

History of the Proth program

- Discovery of the largest known factor of a
Fermat number: 3.2
^{382449}+ 1 divides 2^{2^382447}+ 1 (John Cosgrave). Seven factors have been found since 1997.

History of the Proth program

- PrimeForm is based on Proth.exe library.
- PrimeForm tests probable primality of any
number
*N*. - PrimeForm combines factors
*F*_{1}|*N*-1 and*F*_{2}|*N*+1 with*F*_{1}.*F*_{2}>*N*^{1/3}to test primality of*N*.

Primality tests

- 2
^{p}- 1 : Lucas-Lehmer test (one identity). *k*.2^{n}+ 1 : Proth’s theorem (one identity).*k*.*b*^{n}+ 1 : Pocklington’s theorem (one identity and some inequalities).*k*.*b*^{n}- 1 : Lucas sequences (one identity and some inequalities).

Primality tests

- Fermat’s theorem
*a*^{N-1 }= 1 (mod*N*) can be used as a probable test. - Su Hee Kim and Carl Pomerance considered
the probability that a random probable prime is composite:
1000 digits => 10
^{-123}, 10000 digits => 10^{-1331}

Primality tests

- Hypothesis: a bug generates a random number rather than the correct result.
- Probability that result of Lucas-Lehmer test or Proth’s theorem is false is 1/N.
- Verification of an inequality is difficult: a bug gives generally a correct result.

Primality tests

- To test the primality of a number having
more than 1000 digits, if we use:

- a theorem with some inequalities

- only one sort of hardware and software

then the probability of error is larger than the probability that the probable-prime is prime.

Fast evaluation of tests

- All the known tests have the same
complexity in terms of number of operations: log
_{2}*N*squarings modulo*N*. - The efficiency of a test depends on how
fast we can compute
*x*^{2}(mod*N*). - The form of
*N*is the most important factor.

Fast evaluation of tests

- If
*N*is a random number, we compute, just once, the "reciprocal"*R*= [2^{2s+1}/*N*]. Then to compute*x*^{2}(mod*N*), we evaluate

*m*=*x*^{2}*x*^{2}>>*s*).*R*) >> (*s*+1)).*N .*If FFT multiplications are used, the modular squaring takes about 3 squaring times.

Fast evaluation of tests

- If
*N*is of the form*k*.2^{n}+/- 1, we can quickly compute the modular reduction by remarking that

*x*^{2}/ (*k*.2^{n}+/- 1) =*x*^{2}/ (*k*.2^{n}) -/+*e*with

*e*<= 2.

Then the computation of*x*^{2}(mod*N*) is about as fast as the computation of*x*^{2}.

Fast evaluation of tests

- If
*N*is of the form^{n}+/- 1, we can compute directly*x*^{2}(mod*N*) with some Discrete Weighted Transforms (Crandall and Fagin).

Then the computation of*x*^{2}(mod*N*) is about two times faster than the computation of*x*^{2}.

Fast evaluation of tests

Fast evaluation of tests

- FFT multiplication of
*N*_{1}and*N*_{2}:

- select a base*W.*- find polynomials

*P*_{1},*P*_{2}such that*P*_{i}(*W*)=*N*_{i}. (Fast if base representation of*N*_{i}is*W)*.

- compute*P*=*P*_{1}x*P*_{2}using FFT.

-*N*=*N*_{1}x*N*_{2}=*P*(*W*).

(If base representation of*N*is*W*, we just need to adjust the digits of*N*with add-and-carry).

Fast evaluation of tests

- FFT multiplication are used because it
reduces the complexity of multiplication to
*O*(*n*log*n*log log*n*) [grammar-school:*O*(*n*^{2}), Karatsuba:*O*(*n*^{log 3 / log 2})]. - But it has another important property: the
speed of the FFT multiplication is virtually independent
of the base
*W*.

Fast evaluation of tests

- Proth.exe uses some FFT multiplications
with
*W*=*b*^{m}to test numbers of the form*k*.*b*^{n}+ 1. - For GFN (
*b*^{2n}+ 1), Discrete Weighted Transforms are used with*W*=*b*^{m}.

Fast evaluation of tests

Fast evaluation of tests

*a remark about the
implementation*

- Classical definition of complexity is: number of operations (additions and multiplications). Is it still enough ?
- On modern processors, one operation costs 1 or 1/2 cycle if data is "ready" but it costs 40 cycles to read a data from main memory.

Fast evaluation of tests

*a remark about the
implementation*

- The complexity of a "split-radix FFT" is smaller than a "Four Step FFT".
- The "Four Step FFT" reduces the number of passes through main memory.
- The test of a 100,000 digit number with a "Four Step FFT" is twice faster on a PC.

Actual searches for prime numbers

- Mersenne prime numbers (GIMPS).
- Factors of Fermat numbers (primes of the
form
*k*.2^{n}+ 1). - Cullen (
*n*.2^{n}+ 1) and Woodall (*n*.2^{n}- 1) prime numbers.

Actual searches for prime numbers

- Sierpinski conjecture

(the smallest*k*such that*k*.2^{n}+ 1 is composite for every n is 78557). - Riesel conjecture

(the smallest*k*such that*k*.2^{n}- 1 is composite for every n is 509203). - Generalised Fermat prime numbers.

Actual searches for prime numbers

- Why ?
- To beat some records.
- To verify or discover some conjectures:

- the number of Mersenne primes less than*x*is about (*e^gamma*/ log 2) log log*x*[Wagstaff].

- the probability for*k*.2^{n}+ 1 of dividing a Fermat number is 1/*k*[Dubner and Keller].

Actual searches for prime numbers

- To verify or discover some conjectures:

- what is the distribution of Cullen and Woodall primes ?

- verification of Bateman and Horn’s conjecture (GFN, …). - To prove some theorems (Sierpinski and Riesel conjectures).

Search of tomorrow

- Recent results show that to improve the
searches, we should:

- use many low-cost computers.

- organise and distribute the search over the Internet. - Improvement in the cost-performance of computers and in networks will result in important advances.

Search of tomorrow

- To optimise the process, we can:

- use an automated server.

- look upon the contributors as some customers.

- transform the search into a lottery: the ticket is the loan of CPU time, a prize is given to the contributor who received the "winning" number, luckily.

Search of tomorrow

- How to avoid this grim scenario ?

Will it be possible to keep the jump for joy of the "discoverer" ? - By improving the algorithms (for other forms), we increase the number of "candidates" and we eliminate the need for centralisation of the searches for the largest known prime.