III B 3(c) THE PROOF SUMMARIES lxvi

Back

more complicated strategy that can be implemented using the input control options

of DOWNRUN. A detailed description of the simple strategy is given in [98].

The primes in the table with at most 25 digits were shown to be prime either by

direct search up to their square roots or by DOWNRUN. Since testing for primality

up to this number of digits turns out to be somewhat trivial when the auxiliary

factoring goes up to 106, we have not said anything further about the primality of

these numbers in the tables other than to list them in the main tables. Most primes

and probable primes with more than 25 digits are listed in Appendix A. (See VII

for more information.) The primality proof for each of the primes is summarized

in Appendix B.

In the _nal stages of preparing these tables, the probable primes with at most

72 digits were sent to Hugh Williams, whose powerful testing program can often

routinely settle the primality of numbers up to 80 or even more digits. His programs

found that every large probable prime which we sent to him was prime.

These programs are based on the primality theory which Williams has developed

beyond that detailed in [7]. In his important extensions [107 to 111, 117]

he utilizes properties of extensions of Lucas' and Lehmer's functions, as well as the

factors of the cyclotomic polynomials N2 + N + 1, N2 + 1 and N2 􀀀 N + 1. His

_ne paper [111] on primality testing delineates these extensions in the setting in

which they arise and contains what needs to be said about the form the theory

has taken since the publication of [7]. Because it is a rather complete account of

these matters, we refer the reader to these papers. Further extensions of this kind

appear to require new ideas since the higher cyclotomic polynomials have not yet

been shown to be readily applicable to primality testing. However, some work in

this direction is now being done. See section IV A 3.

A few prime proof summaries based on proofs due to others have been included

in Appendix B.

(c) The Proof Summaries. The notation in the proof summaries that are listed

in Appendix B employs the following abbreviations and signs:

PPL Proth-Pocklington-Lehmer. The proof was made using Theorems

1, 2 and the Corollary in [98, p. 110] and the prime factors of N􀀀1.

CMB Combined Theorem. The proof was made using Theorems 3 and 4

in [98, p. 110] and prime factors of N 􀀀1 and N +1. The extra 2,

mentioned in Theorem 12, was used if needed.

BLS7 Theorem 7 of [7]. The proof was made using Theorem 11 above.

(This notation was not used in the _rst edition. See IV A 3(c).)

p A prime factor p > 106, given as a \hint". It is followed by an

M, P, F3, F4 or F6, indicating it is respectively a factor of N 􀀀 1,

N +1, N2+N +1, N2+1 or N2􀀀N +1 at some level. This factor,

which was discovered by one of the auxiliary factoring programs,

is input with the number to be tested and is used to complete the

primality test.

Example. 34 10,49􀀀 201457393P CMB

Here the hint is the prime 201457393 which is a factor of N + 1.

(n) This notation, placed after PPL or CMB, indicates the direct

search had to be taken to n, instead of the standard 106, in order

to obtain a su_ciently large search bound to complete the proof.

lxvii III B 3(c) THE PROOF SUMMARIES

Example. *115 3,287􀀀 42521761M CMBF4F6(10**8)

The combined theorem proves the primality using a hint on the

minus side. Some small factors of F4 and F6 and the factor bound

108 are used in the proof. (There were many proofs with search

bounds > 106 in the _rst edition, but most were simpli_ed in the

second edition.)

(* This proof is due to Hugh Williams.)

􀀀,+ A minus sign indicates the cofactor R1 of N 􀀀1 is a probable prime

base 13 and the program, after _nishing its testing of N assuming

that R1 is a prime, went down and then showed that R1 actually

is a prime by carrying out a primality test on it. (See 3(a)(4).) A

plus sign means the same, but for the cofactor R2 of N + 1.

Example. 40 2,278M +􀀀CMB

Here, after removal of the factors 2:32:5:157 from N + 1 (the plus

sign), we obtain the probable prime

R2 = 88546630665248948043897559039615307

and then with the removal of the factors 2:7:233 from R2 􀀀 1 (the

minus sign), we have the probable prime

R = 27144889842197715525413108227963

which was proved to be prime using the combined theorem.

Example. 58 2,329􀀀 􀀀+􀀀􀀀􀀀􀀀CMB

Here the program descended 6 times before it was able to complete

the test on this 58-digit cofactor of 2329 􀀀 1.

Examples. 50 10,190M 6129730457M 􀀀PPL

52 2,289􀀀 +80216641M CMB.

In the _rst example the hint is removed from N 􀀀 1 and then

the probable prime cofactor is tested for primality. In the second

example, the hint is used only after the program goes down on the

plus side.

Mersenne This Mersenne number has been proved prime by the standard

test, Theorem 6, 3(a)(7) above.

(5**58+1)/26 M This indicates that the prime (558 + 1)=26 is to be used as a hint

on the minus side. There are also other hints of this type given

in Appendix B, always for large numbers, where the primality test

becomes easy with this information. Other examples, which vary

slightly in format, are:

83 6,107+ Cofactor of 6**53 􀀀 1 M CMB

89 2,447􀀀 Alg.PPL See [7]

231 2,1149+ Factors of 2**382 􀀀 1 PPL

Example. 178 2,745􀀀 Factors of 2**148􀀀1 􀀀􀀀􀀀1317031M

89165962987803776023M BLS7.

After factors dividing N 􀀀 1, the program goes down three times

on the minus side. The proof was completed by the Cube Root

Theorem with two hints on the minus side.

III C 1 ALGEBRAIC AND PRIMITIVE FACTORS lxviii

Навигация