The Proth program and the search for prime numbers

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ⁿ + 1).
Several implementations were evaluated.
In 1997, Carlos Rivera discovered 9183.2²⁶²¹¹²+ 1 (largest known "non-Mersenne" prime).

History of the Proth program

In 1998, largest known "Sophie Germain" prime: 92305.2¹⁶⁹⁹⁸+ 1 (Chip Kerchner).
Program was extended to also cover the form k.2ⁿ - 1.
Largest known twin primes 835335.2³⁹⁰¹⁴+/-1 (Ray Ballinger) and "Sophie Germain" prime: 72021.2²³⁶³⁰-1.

History of the Proth program

In 1998, major "theoretical" improvement: ability to test k.bⁿ + 1, for small b, in about the same time as a number k.2ⁿ + 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²ⁿ + 1) was implemented: test of a GFN is up to 2 times faster than a number k.2ⁿ + 1 of the same size.

History of the Proth program

Discovery of the largest known factor of a Fermat number: 3.2³⁸²⁴⁴⁹ + 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₁ | N-1 and F₂ | N+1 with F₁.F₂ > N^1/3 to test primality of N.

Primality tests

2^p - 1 : Lucas-Lehmer test (one identity).
k.2ⁿ + 1 : Proth’s theorem (one identity).
k.bⁿ + 1 : Pocklington’s theorem (one identity and some inequalities).
k.bⁿ - 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₂ N squarings modulo N.
The efficiency of a test depends on how fast we can compute x² (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² (mod N), we evaluate
m = x² - (((x² >> 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ⁿ +/- 1, we can quickly compute the modular reduction by remarking that
x² / (k.2ⁿ +/- 1) = x² / (k.2ⁿ) -/+ e
with e <= 2.
Then the computation of x² (mod N) is about as fast as the computation of x².

Fast evaluation of tests

If N is of the form 2ⁿ +/- 1, we can compute directly x² (mod N) with some Discrete Weighted Transforms (Crandall and Fagin).
Then the computation of x² (mod N) is about two times faster than the computation of x².

Fast evaluation of tests

FFT multiplication of N₁ and N₂ :
- select a base W.
- find polynomials P₁, P₂ such that P_i(W)= N_i. (Fast if base representation of N_i is W).
- compute P = P₁ x P₂ using FFT.
- N = N₁ x N₂ = 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²), 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ⁿ + 1.
For GFN (b²ⁿ + 1), Discrete Weighted Transforms are used with W = b^m.

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ⁿ + 1).
Cullen (n.2ⁿ + 1) and Woodall (n.2ⁿ - 1) prime numbers.

Actual searches for prime numbers

Sierpinski conjecture
(the smallest k such that k.2ⁿ + 1 is composite for every n is 78557).
Riesel conjecture
(the smallest k such that k.2ⁿ - 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ⁿ + 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.