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-2,
f; here
f 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 and quotient
q are defined by the relations
N =
r
+
f.
q, 0 ≤
r <
f.
Now q is divided by f + 2, giving
q
=
r + (
f
+ 2).
q, 0 ≤
r <
f + 2 .
Then q
is divided by (
f + 4) etc. and this process is continued till a quotient
(q say) equal to zero is found;
r is the last remainder in the sequence unequal to zero. After elimination of the
q we get the relations
N
= r
+ f.r
+ f.(f+2)r
+ f.(f+2).(f+4)r + ... + f.(f+2)
... (f+2n-2).r | (1) |
and
Once the sequence r is known for a given value of f, it is easy to compute the corresponding sequence
r, defined by the relations (1) and (2) with respect to
f = f + 2, as they are expressed in terms of the
r by the recurrence relations
b = 0,
r
= r
- 2(i+1)r - b + (f+2i)b (i = 0, 1, ..., n) | (3) |
The relation corresponding to (1) is satisfied for arbitrary values of the numbers
b with i ≥ 1; they are fixed, however, by the relations corresponding to (2)
On account of the inequalities (2) and (2*) —and
b
= 0— the b satisfy the inequalities
We have chosen b = 0.
Then the relations (3) and (2*) with i = 0 determine
r and
b; once
b is known, (3) and (2*) with i = 1 determine
r and
b, etc. The process is easily programmed.
[unreadable] 0, and the inequalities (2*) with i = n are always satisfied with
b = 0, the process terminates with
As soon as r = 0 is found —in that case it can be proved, that
r
≠ 0— the index n, marking the last r ≠ 0 in the sequence, is lowered by 1.
In order to find the smallest odd prime factor of N, the r 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 ≈ 10^{13}. The amount of work involved in each step is roughly proportional to n^{2}. 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 = 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 earlier and should have stopped there.)
The process still may be speeded up. Let
b be the minimum of
b for fixed n up till a certain moment: then it can be shown that the next
b satisfies
Let us apply this to the last stage n = 2. According to (4) b satisfies
0 ≤ b ≤ 4. According to (5), however, the only possible values for
b are 0 and 1 as soon as a value
b = 0 once has been found. This is bound to happen for f ranging (roughly) from
(4N) till
(8N). In the case
b = 0 it is apparently unnecessary to test whether
r = 0 is reached. (If N ≥ 144, the case
b = 0 with n = 2 occurs, before
r = 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).) 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 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 "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.