3. Developments in Primality Testing.

Back

In this section we give an account of the primality tests that have been used in

building these tables. This account is more detailed than that of the preceding section,

because it is almost impossible, by studying the literature alone, to determine

how these primality testing methods developed.

(a) The Theory. By a \primality test" we shall always mean a rigorous proof of

primality, and not a probabilistic method for asserting the likelihood of primality.

That is, by a \primality test" on a number N, we mean an algorithm whose steps

consist of verifying the hypotheses of a theorem whose conclusion is \N is prime."

Thus, _nding that the results at each step of the algorithm are true for N, we

conclude that N must be a prime.

(1) Trial Division. Certainly the oldest way to prove a number prime is to show

by trial division that it has no nontrivial factor less than or equal to its square root.

If, however, a number N is too large for trial division alone to be practical, one

_rst asks whether N satis_es Fermat's congruence

(1) aN􀀀1 _1 (modN)

for some base a, 1 < a < N 􀀀 1. Fermat's congruence is a necessary but not a

su_cient condition for primality. If it holds for an odd N > 1, we call N a probable

prime base a and write \PRP(a)" or just \PRP". Many authors, including

ourselves, have previously used the misnomer \pseudoprime" for "probable prime".

We now use \pseudoprime" only for a composite number satisfying (1).

III B 3(a) THE THEORY lx

When N satis_es (1), one should try to complete a primality test on N rather

than try to factor it. There is almost no chance that it is composite. In practice such

composite N are almost never encountered; but when they are, we greet these true

novelties with pleasure and curiosity. (See [6, p. 91].) Recently Carl Pomerance,

JLS and SSW [82, p. 1024] suggested that augmenting one Fermat test with one

speci_c test of the Lucas type might be a fast test for primality. No composite

number is known which passes this pair of tests, but they have not proved that

no such number exists. All of the probable primes in the tables have passed this

speci_c test, giving convincing evidence, but no _nal proof, that they are primes.

The computing was done by SSW.

(2) Fermat's Method. Factoring methods generally rely upon exhaustive trials

of values in certain sequences. The di_erence of squares factoring method discussed

in 2(c) provides an example.

Here N = ab = x2 􀀀 y2 where the nontrivial p values of x lie in the interval

N <x < 1

2 (B + N

B ), where B is the direct search bound. If no x in this interval

gives a factor of N, then N must be a prime. Often whole collections of x values

can be disposed of without trying them by imposing necessary conditions on x, as

in the quadratic exclusion method (a quadratic sieve) of Gauss. An example of this

method can be found in [43].

(3) Euler's Method. Euler showed that if an odd number N can be expressed

as a sum of two squares in essentially only one way, then N is prime. This has been

used as a means of testing for primality when the number of possible representations

could be scanned completely.

(4) Converses of Fermat's Congruence. E. Lucas [71, p. 302; 72, p. 441]

published two somewhat ine_ective converses of (1), but the _rst really e_ective

converse theorems for testing primality were published by M. Kraitchik [34, p. 135]

and DHL [40, p. 330].

Theorem 1. If there exists an a for which aN􀀀1 _ 1, but

a(N􀀀1)=q 6_ 1 (mod N) for each prime factor q of N 􀀀 1, then

N is prime.

The e_ectiveness of this theorem for large N arises from the fact that the

needed remainders can be calculated in roughly log2 N multiplications and divisions

[60, p. 124]. Although several bases may have to be tried among the numbers for

which the Jacobi symbol (ajN) = 􀀀1 before a single a is found for which all the

hypotheses of Theorem 1 are satis_ed, the main di_culty in using the theorem is

that all the prime factors q of N 􀀀 1 must be found; but when N 􀀀 1 could be

factored, this theorem was often implemented. For example, the primality of the

49-digit factor N of 2179 􀀀1 was proved, with a = 19, from

N 􀀀1 = 24:3:5:7:41:163:179:643:919:43399:1071379:23262667:1159540629640123 :

Using Theorem 1 at two levels [4] gave the primality of the 37-digit factor N of

2181 􀀀 1, since N 􀀀 1 = 2:5:181:M, where M, a probable prime base 19, can be

proved to be prime from the factorization

M 􀀀 1 = 2:3:47:253567:811039:2293751:32910082955041 :

The standard test for primality of the Fermat number Fn = 22n + 1 is the

subject of the next theorem.

lxi III B 3(a) THE THEORY

Theorem 2. (P_epin [78]) The Fermat number Fn is prime for

n _ 1 if and only if 3(Fn􀀀1)=2 _ 􀀀1 (mod Fn).

This test is well suited to binary computers [90], and see [40], p. 334], for

the powering is pure squaring and the reductions (mod Fn) can be accomplished

without dividing by noting that

A:22n + B = A(22n + 1)+(B 􀀀 A) _ B 􀀀 A (mod Fn)

(5) Proth's Theorem. In [85], E. Proth published the following important

generalization of P_epin's theorem.

Theorem 3. Let N = k:2n + 1, where 1 _ k < 2n. If

a(N􀀀1)=2 _ 􀀀1 (mod N) for some a, then N is prime.

The importance of this theorem, beyond its immediate application to numbers

of certain forms, is that the complete factorization of N 􀀀 1 is not needed to _nish

a primality test on N.

Theorem 3 was used in [3] by DHL for the primality testing of the numbers

N = 2p _ 2(p+1)=2 + 1, where p is prime. Here the power of 2 in N 􀀀 1 is larger

than the cofactor, so the test can be made by Proth's theorem. For example, the

number 2457 􀀀 2229 + 1 was proved to be prime in this way.

Rather than computing the required remainders (mod N) directly, the reductions

in powering were _rst made with respect to the intermediate modulus

22p +1 = (2p 􀀀2(p+1)=2 +1)(2p +2(p+1)=2 +1), using the scheme mentioned in (4),

and then with respect to the actual modulus N.

Sometimes the algebraic form of N readily yields the factorization of N􀀀1. For

example [3], and see [40, p. 329] and [54]], for certain p, 5 divides 2p _2(p+1)=2 +1

and the quotient N is a probable prime. For such p we then have

N 􀀀 1 = 4[2(p􀀀1)=2 _ 1][2(p􀀀3)=2 _ 1]=5 :

(6) Pocklington's Theorem. This theorem of 1914 is of great importance in the

primality testing of numbers which are not of any special form.

Theorem 4. Suppose that N 􀀀1 = qnR, where q is a prime and

q -R. If a is such that aN􀀀1 _ 1 (mod N) and (a(N􀀀1)=q 􀀀1;N)

= 1, then each prime factor p of N satis_es p _ 1 (mod qn).

Although this theorem does not mention primality explicitly, it does give valuable

information about the form of possible factors of the probable prime N. This

theorem is stronger than Theorem 1, for the condition (a(N􀀀1)q 􀀀1;N) = 1 is more

stringent than the condition a(N􀀀1)=q 6_ 1 (mod N).

The _rst and most immediate application of this theorem is to combine the

modular conditions on p for di_erent divisors of N 􀀀 1. For instance, if qm

1 and

qn

2 divide N 􀀀 1 and the hypotheses in Theorem 4 are satis_ed, then any prime

factor of N will be congruent to 1 (mod qm

1 qn

2 ). Accordingly, we have the following

primality test.

Corollary 1. Suppose N 􀀀 1 = FR, where F is completely

factored, F > R and (F;R) = 1. If there exists an a for which

aN􀀀1 _ 1 (mod N), but (a(N􀀀1)=q 􀀀 1;N) = 1 for each prime

factor q of F, then N is prime.

III B 3(a) THE THEORY lxii

This result is a very practical primality test, which for large N almost certainly

will show that N is prime when enough prime factors of N 􀀀1 have been found for

their product F to exceed R = (N 􀀀1)=F. In fact, this corollary is a generalization

of Theorem 3, where the factored part is just a power of 2.

This corollary was used in many of the primality tests for numbers in these

tables. Moreover, Theorem 4 can sometimes be useful in showing that N is prime

even when F < R. For, if F is not too small, a direct search can sometimes be

made with the terms of the sequence kF + 1 to show that N has no factor _

p

N.

(Some divisors in this sequence can be eliminated in advance by sieving with small

primes.) This method was used in [40] to show that N = 440334654777631, the

cofactor of 1027 􀀀 1, is a prime. (The correct remainders mod N of 3(N􀀀1)=5 and

3(N􀀀1)=52189481 are 313433259338997 and 78523825886276 respectively.)

Another way to use the form of the factors of N in case F < R is to introduce

this information into a di_erence of squares factorization, with the hope of

cutting the possible values of x to only a few or none. This method was introduced

and used in [40], where, for example, the number N = (1031 + 1)=11 =

909090909090909090909090909091 could be shown to be prime because of the fortunate

factorization of N 􀀀1 = 10(1030􀀀1)=11. (See [41, 43] for other examples.)

(7) Lucas' Theorem. In 1878 [71, p. 302] E. Lucas published a theorem which

permitted the complete factorization of N + 1 to be used for primality testing in a

way comparable to that of N 􀀀 1. To do this he introduced a pair of second order

recurring sequences (now called Lucas sequences) de_ned as follows:

Un+2 = PUn+1 􀀀 QUn; U0 = 0; U1 = 1;

Vn+2 = PVn+1 􀀀 QVn; V0 = 2; V1 = P;

where P and Q are integers. Also, we let D = P2􀀀4Q and "N = (DjN), where the

latter is the Jacobi symbol. With this theorem made e_ective by using only prime

divisors q as in Theorem 1, we have the theorem of DHL [44, p. 442].

Theorem 5. If NjUN􀀀"N , but N - U(N􀀀"N)=q for each prime q

dividing N 􀀀 "N, then N is prime.

If P and Q, and therefore D, are chosen so that "N = 􀀀1, then the hypotheses

relate to N + 1. The choice of Lucas sequence here compares with the choice

of base in the N 􀀀 1 theorems. That is, one experiments with choices P and Q

until the sequence allows all the hypotheses to be satis_ed. This theorem requires

the computation of remainders (mod N) for terms with large subscripts. Lucas

sequences satisfy many useful identities. For example, to compute Um (mod N)

one can use

U2n = UnVn;

V2n = V 2

n

􀀀 2Qn;

U2n+1 = (PU2n + V2n)=2;

V2n+1 = (DU2n + PV2n)=2:

The test in Theorem 5 was programmed by DHL for the IBM 7094 with

P = 1 and Q chosen so that "N = 􀀀1. This program was used to demonstrate

the primality of the 24-digit factor N of 2109 􀀀 1, using Q = 5. Here

lxiii III B 3(a) THE THEORY

N + 1 = 2:3:67:83:233:M, where M was shown to be prime by Theorem 1, with

a = 3, from M 􀀀 1 = 2:3:503:1801:7643:2693893. The theorem was also used

[6] at several levels to show the primality of the 38-digit factor N of 2131 �� 1.

The factorization N + 1 = 2:3:5:72:112:2711:N1 was used with Q = 17, the factor

N1 being shown prime with Q = 29 and N1 + 1 = 2:33:892:30211:N2, where

N2 is in turn shown to be prime with Q = 􀀀1 from the complete factorization

N2 + 1 = 22:389:22901:46616380229.

The most familiar use of Lucas sequences is for testing the primality of Mersenne

numbers. This was initiated by Lucas [71, pp. 305, 316] and made into a

simple test by DHL in [44, p. 443]; see also [51].

Theorem 6. For p odd, the Mersenne number Mp is prime if and

only if MpjSp􀀀1, where Sn+1 = S2n

􀀀 2, S1 = 4.

This test, like the one for Fermat numbers (Theorem 2), can be carried out

without dividing, because A:2p + B = A(2p 􀀀 1) + (A + B) _ A + B (mod Mp).

This well-known Lucas-Lehmer test has been used for all the modern testing of

these numbers [90, 86, 28, 22, 102, 76, 101].

(8) A \Lucas-Pocklington" Theorem. As Pocklington's theorem is so important,

it was reasonable to look for an analogous theorem for Lucas sequences. This was

proved by DHL [44, p. 443].

Theorem 7. Let N+1 = qnR where q is prime and q -R. If fUng

is a Lucas sequence for which NjUN􀀀"N and (U(N􀀀"N)=q;N) =

1, then each prime factor p of N satis_es p _ _1 (mod qn).

As in Theorem 5, we choose a sequence with "N = 􀀀1 so that N + 1 appears

in the subscripts. However, in this theorem the factors p belong to the two residue

classes _1 (mod qn) for each prime divisor q in N + 1, which cannot be combined

immediately into these two classes (mod F), where F is the product of the moduli.

In fact, it was long thought that if s of these congruences were combined by the

Chinese remainder theorem, the best that could be said about a prime factor p of N

was that it belonged to one of 2s di_erent residue classes (mod F). This apparent

di_culty blocked the development of Lucas analogues for theorems on the \minus"

side [44, p. 443, footnote].

It therefore came as a considerable surprise when Mike Morrison [74] proved

that even though there are 2s possible ways of combining the individual congruences,

it is nonetheless true that each prime factor p of N satis_es p _ _1 (mod F).

The following result opened the way to developing the \plus" side theorems.

Theorem 8. Suppose that N + 1 = FR, where F is completely

factored and (F;R) = 1. If there exists a Lucas sequence fUng

for which NjUN+1 and (U(N+1)=q;N) = 1 for each prime factor

q of F, then each prime divisor p of N satis_es p _ _1 (mod F).

We learned recently that a result equivalent to Theorem 8 appears in Riesel

[118, page 59, Sats 3.7].

(9) Change of Base or Sequence. The Extra 2. In the summer of 1964, JLS and

JB were working together at UCLA. Out of this collaboration came two important

ideas in primality testing. The _rst is a theorem of JLS [6, p. 89].

Theorem 9. If N 􀀀 1 is completely factored and for each qi

dividing N 􀀀1 there exists an ai for which aN􀀀1

i

_ 1 (mod N),

but a(N􀀀1)=qi

i

6_ 1 (mod N), then N is prime.

Навигация