III B 3(b) THE PROGRAMS

Back

during the factoring of N 􀀀 1 for 2F3 + 2F to exceed N, then the primality test

can be completed. In all the improvements that have been mentioned so far, the

thrust has been to eliminate unnecessary computing or to replace time-consuming

factoring by powering or GCD's.

(12) The Joint Paper of 1975. The major plan in [7] was to use the factorization

of N + 1 in parallel to that of N 􀀀 1. The many di_erent ideas:

(a) Morrison's theorem on the \plus" side,

(b) change of base and change of Lucas sequence,

(c) the extra 2,

(d) the factor bound,

(e) the cube root theorem,

coalesced into the powerful combined theorem of JLS [7, Theorem 20 and its

Corollary 11]. Further slight sharpening has resulted in the following form of the

combined theorem.

Theorem 12. Let N 􀀀 1 = F1R1 and N + 1 = F2R2, where

F1, F2 are complete factorizations and R1, R2 are composite

numbers with no factors less than B1, B2, respectively, and

de_ne G = max(B1F1;B2F2 􀀀 1). If N < GB1B2F1F2=2, then

N is prime if it passes the powering and GCD tests analogous to

those of Theorems 7 to 11. The denominator 2 may be omitted if

N = 4k+1 and B1F1 > B2F2 or if N = 4k􀀀1 and B2F2 > B1F1.

(b) The Programs. Most of the numbers marked as primes in these tables have

been shown to be prime by the program DOWNRUN. This program was written by

JLS and MarvinWunderlich and is used in conjunction with two auxiliary factoring

routines whenever a more powerful factoring program than DOWNRUN is needed.

The factoring routines are the continued fraction program of JB and Mike Morrison

and a single step Pollard p 􀀀 1 routine. The continued fraction program is the

automated version due to Wunderlich that can factor a number of up to 43 digits

in a couple of hours.

DOWNRUN begins its work by _nding all factors of N 􀀀1 and N+1 below the

direct search bound. These numbers are factored simultaneously. If no complete

factorization of N 􀀀1 or of N +1 is found, then the product of their known factors,

along with the bound, is tried in the inequalities of Theorems 10 or 12. If neither

of the cofactors R1, R2 of N _ 1 is a probable prime base 13, the direct search is

continued to 106 and the same procedure is repeated.

If R1 or R2 is found to be a probable prime, then the program goes down and

does not presently come back up to the same level again. Thus, it can happen when

both R1 and R2 are probable primes and R1 < R2 that the possibilities for R2 are

not explored because the program went down on the minus side and was not able

to complete the primality test. There is an option in the program, however, that

permits the user to select the side on which the program may go down.

The program is also set up to accept factoring hints to help it in completing

the proof. The simple yet incomplete strategy used in DOWNRUN is based on the

practical observation that all but the larger numbers will automatically be processed

using this simple strategy. The larger numbers can then be handled by designing a

Навигация