III B 3(a) THE THEORY lxiv

Back

This theorem is an improvement on Theorem 1, since if an a can be found for

which aN􀀀1 _ 1 (mod N), but a(N􀀀1)=q 6_ 1 (mod N) for a particular q, then that

q has been settled once and for all regardless of what bases are used for the other qi.

Thus, it is no longer necessary to _nd a single base a for which all the hypotheses

are satis_ed. This idea carried over into all the other theorems on the minus side

[7, pp. 621{623]. On the plus side, JB suggested that if a change in sequence were

needed, then another Lucas sequence should be tried with the same D. This can

easily be done by the transformations P1 = P +2 and Q1 = P +Q+2. Using these

ideas, it was possible to develop \change of sequence" theorems on the plus side

that paralleled the change of base theorems on the minus side [7, pp. 629{631].

The second idea has to do with an extra factor of 2 that JB inadvertently put

in the modulus of a di_erence of squares sieve setup for factoring. When the factor

was found, JLS proved by a parity argument that the extra 2 should indeed be there.

Later JB proved the general rule [6, p. 89] \: : : the modulus can be increased by

a factor of 2 if (N 􀀀 1)=n is odd." Although this extra two in the modulus made

the search for x go twice as fast and is therefore a useful improvement in di_erence

of squares factoring whenever it can be made, it was to play an important role in

primality testing, where the double modulus gave a correct size remainder in the

theory. (See [7, eqs. (9) and (19)].)

(10) Introduction of the Search Bound. In 1966, DHL found a way of introducing

into primality theory the information that N 􀀀 1 has no factor below a certain

bound. In its original, unpublished form (it _rst appeared in [7, p. 625] in the midst

of the ideas that are developed there) it was expressed as follows:

Theorem 10. Let N 􀀀1 = FR, where F is completely factored

and (F;R) = 1. If there is an a for which aN􀀀1 _ 1 (mod N),

(aF 􀀀1;N) = 1, and (a(N􀀀1)=q􀀀1;N) = 1 for each prime factor

q of F, and if all the prime factors of R exceed

p

R=F, then N

is prime.

Note that the new element here is the GCD condition (aF 􀀀 1;N) = 1. It

should be emphasized that

p

R=F is a bound on the size of the factors of the

auxiliary factorization of N 􀀀 1 and not on N itself.

(11) The Cube Root Theorem. A major improvement in primality testing was

introduced by JLS in 1970, when he analyzed di_erence of squares techniques in

primality testing. He observed that if the _rst trial divisor did not divide N (highly

unlikely since N was a probable prime), then the next one was so much larger that

proof of primality required the factoring of N 􀀀 1 only up to the cube root of N.

What follows is an early form of this theorem.

Theorem 11. Let N 􀀀1 = FR, where F is completely factored

and (F;R) = 1. Suppose there exists an a for which aN􀀀1 _ 1

(mod N) and (a(N􀀀1)=q 􀀀 1;N) = 1 for each prime factor q of

F. Let R = rF + s, 1 _ s < F, and suppose N < 2F3 + 2F,

F > 2. If r is odd, or if r is even and s2 􀀀 4r 6= t2, then N is

prime. Otherwise, s2 􀀀 4r = t2 and

N = [1

2 (s 􀀀 t)F + 1][1

2 (s + t)F + 1]:

It is clear that all the computations that are required in this theorem are

practical, being either powers or GCD's. As soon as F becomes large enough lxv

Навигация