STICHTING
MATHEMATISCH CENTRUM
2e BOERHAAVESTRAAT 49
AMSTERDAM

ZW 1957-002

Voordracht in de serie "Actualiteiten"

E.W. Dijkstra

Zaterdag 26 januari 1957

A method to investigate primality 1957

Voordracht in de serie "Actualiteiten"
door
E.W. Dijkstra
op
Zaterdag 26 Januari 1957

A method to investigate primality

The method determines the smallest odd prime factor of a number N by testing the remainders left after division by the successive odd numbers 3, 5, ... f
 m
-2
, f
 m
;
here f
 m
is the largest odd number not exceeding N½. If none of these remainders vanishes, N is a prime number.

Let f be one of the odd divisors or odd trial divisors. Remainder r
 0
and quotient q
 0
are defined by the relations

N = r
 0
+ f.q
 0
,           0 ≤ r
 0
< f.

Now q
 0
is divided by f + 2, giving

q
 0
= r
 1
+ (f + 2).q
 1
,       0 ≤ r
 1
< f + 2 .

Then q
 1
is divided by (f + 4) etc. and this process is continued till a quotient (q
 n
say) equal to zero is found; r
 n
is the last remainder in the sequence unequal to zero. After elimination of the q
 i
we get the relations
N = r
 0
+ f.r
 1
+ f.(f+2)r
 2
+ f.(f+2).(f+4)r
 3
+ ... + f.(f+2) ... (f+2n-2).r
 n
(1)
and
0 ≤ r
 i
< f + 2i
(2)

Once the sequence r
 i
is known for a given value of f, it is easy to compute the corresponding sequence r
 *i
,
defined by the relations (1) and (2) with respect to f
 *
= f + 2,
as they are expressed in terms of the r
 i
by the recurrence relations
b
 0
= 0, r
 *i
= r
 i
- 2(i+1)r
 i+1
- b
 i
+ (f
 *
+2i)b
 i+1
(i = 0, 1, ..., n)
(3)

The relation corresponding to (1) is satisfied for arbitrary values of the numbers b
 i
with i ≥ 1; they are fixed, however, by the relations corresponding to (2)
0 ≤ r
 * i
< f
 *
+ 2i .
(2*)

On account of the inequalities (2) and (2*) —and b
 0
= 0
— the b
 i
satisfy the inequalities
0 ≤ b
 i
≤ 2i .
(4)

We have chosen b
 0
= 0.
Then the relations (3) and (2*) with i = 0 determine r
 *0
and b
 1
;
once b
 1
is known, (3) and (2*) with i = 1 determine r
 *1
and b
 2
,
etc. The process is easily programmed. [unreadable] 0, and the inequalities (2*) with i = n are always satisfied with b
 n+1
= 0,
the process terminates with
r
 * n
= r
 n
- b
 n

As soon as r
 *n
= 0
is found —in that case it can be proved, that r
 *n-1
≠ 0—
the index n, marking the last r
 i
≠ 0
in the sequence, is lowered by 1.

In order to find the smallest odd prime factor of N, the r
 i
defined by (2) and (3) and f = 3 are computed. Here the only divisions in the process are carried out. At the same time the initial value of n is found. If N is large, this value may be considerable: for instance n = 11 is found for N ≈ 1013. The amount of work involved in each step is roughly proportional to n2. Fortunately large initial values of n decrease very rapidly. As soon as f.(f + 2).(f + 4) > N, n takes the value 2. This is its minimum value: when r
 * n
= 0
with n = 2 is found (f
 *
+ 2)2 > N
holds and N is a prime number. (If not, we should have found a r
 0
= 0
earlier and should have stopped there.)

The process still may be speeded up. Let b
 'n
be the minimum of b
 n
for fixed n up till a certain moment: then it can be shown that the next b
 n
satisfies
b
 n
b
 'n
+ 1 .
(5)

Let us apply this to the last stage n = 2. According to (4) b
 2
satisfies 0 ≤ b
 2
≤ 4.
According to (5), however, the only possible values for b
 2
are 0 and 1 as soon as a value b
 2
= 0
once has been found. This is bound to happen for f ranging (roughly) from (4N)
 1/3
till (8N)
 1/3
.
In the case b
 2
= 0
it is apparently unnecessary to test whether r
 2
= 0
is reached. (If N ≥ 144, the case b
 n
= 0
with n = 2 occurs, before r
 *n
= 0
with n = 2 is found: prime numbers are then always detected in this last stage.)

The less efficient steps of the process for large n (i.e. small f) could be avoided by carrying out divisions for small values of f. (Cf. the method suggested by G.G. Alway, MTAC v. 6, p. 59-60, where one seems to be obliged to do this for f up to (8N)
 1/3
.)
However we strongly advise not to do this.

If the process described above is started at f = 3, the whole computation can be checked at the end by inserting the final values of f and r
 i
into (1). As all the intermediate results are used in the computation, this check seems satisfactory.

If a double length number N is to be investigated, another argument can be added: division of N by small f may give a double length quotient, i.e. two divisions (and two multiplications to check) are needed for each f. In our case even only part of the initial n divisions are double length divisions.

If some consecutive odd numbers are to be investigated, the initial divisions are only necessary for the first number N; it is easy to compute the sequence of initial remainders r
 i
"representing N + d at f = 3" from the corresponding sequence for N at f = 3, if d is small.

The process described above has been programmed for the ARMAC (Automatische Rekenmachine van het MAthematisch Centrum). The speed of this machine is about 2400 operations per second. A twelve decimal number was identified as the square of a prime in less than 23 minutes.