2. Developments in Factorization.

Back

\The problem of distinguishing prime numbers from composite

numbers and of resolving the latter into their prime factors is

known to be one of the most important and useful in arithmetic.

It has engaged the industry and wisdom of ancient and modern

geometers to such an extent that it would be superuous

to discuss the problem at length. Nevertheless we must confess

that all methods that have been proposed thus far are either

restricted to very special cases or are so laborious and prolix

that even for numbers that do not exceed the limits of tables

constructed by estimable men, i.e. for numbers that do not yield

to arti_cial methods, they try the patience of even the practiced

calculator: : : The dignity of the science itself seems to require

that every possible means be explored for the solution of a problem

so elegant and so celebrated." C. F. Gauss [21, Sec. 329]

In the past, before electronic computers, only a few factors of the numbers in

these tables were discovered in a year's time, and a record was kept of who had

discovered the factors. Computers have made factorization such a proli_c activity

that exhaustive documentation is, of course, no longer practicable. Accordingly, we

mention only a few outstanding cases in this Introduction and make no attempt at

all to document the tables themselves. A few factors in the tables have appeared

earlier in privately circulated lists of E. Karst and M. Merson. (See [6, 7, 30].)

After the extensive searches for factors that we conducted, a _nal search by

SSW put the tables in almost _nal form for publication. This was a direct search

made after the compilation and distribution of a _rst version of the tables in 1976

to a few interested parties. In this search all the numbers in the tables were refactored

up to a common search limit of 235. With the known factors having been

rediscovered and the new factors entered in the tables, we are con_dent that the

tables contain all prime factors less than 235.

In this section, we limit our discussion to the factoring methods we have actually

used, since, as mentioned before, this is not a history of the subject, but rather

an account of the building of these tables.

III B 2 DEVELOPMENTS IN FACTORIZATION lvi

(a) Direct Search. This \divide and conquer" method (most often more divide

than conquer) is a factoring method in which a sequence of trial divisors is generated,

usually in order of increasing magnitude. Each member of the sequence,

less than some factoring bound, is divided into the number N to see if it divides

exactly.

The most common method of generating the sequence of trial divisors is with

the use of an increment table. The increments in the table are the remaining

di_erences after certain terms in the appropriate arithmetic sequence are sieved

out because they are multiples of small primes. These primes usually don't exceed

13 because of space limitations in the computer [92, 2]. The table of increments

is _rst constructed by the computer and is then used over and over again to create

the sequence of trial divisors.

Although composite trial divisors remain in the sequence, it is more practical

just to try them as possible divisors than to spend time eliminating them, unless

trying one of them is very time-consuming. In [26] the authors found it better to

use an extensive sieve and eliminate most composite numbers from the sequence of

trial divisors.

Perhaps the simplest way to program the construction of the increment table

is through the use of a GCD subroutine, which rejects a member of the arithmetic

sequence to which the factors belong if it has a factor in common with any of the

sieve primes. A good check on the increment table is to sum its entries. In the

direct search to 235, SSW did not use an increment table. To seek small factors of

2p 􀀀 1, for example, he chose J so that 8pJ was a reasonable size, say 8pJ _ 105

with J the product of small odd primes. Then for each appropriate S _ 8pJ

with (S; J) = 1, the trial divisors f = S + 8pJk, k = 0; 1; 2; : : : ; were tested in

that order for f < 235. This strategy kept the memory requirements small. Here,

\appropriate" means that if N has a particular form, the sequence to which the

factors belong may be severely restricted. For example, if N = 2p 􀀀 1, p prime,

all factors are of the form kp + 1 and 8k _ 1. For another example, the possible

prime factors q of _n(b), apart from a possible intrinsic factor, must belong to the

arithmetic progression q _ 1 (mod n) if n is even, or q _ 1 (mod 2n) if n is odd.

(See section C.)

A direct search is usually made to try to _nd small prime factors of N before

anything else is done. When the factors less than the search bound are removed,

then the remaining cofactor (again called N) is tested in Fermat's congruence to

determine if N is composite or if N is a probable prime, i.e., a number that

satis_es Fermat's congruence for some nontrivial base.

(b) Legendre's Method. In this method the sequence of trial divisors is obtained

by using a much more elaborate sifting method, a quadratic sieve. By using quadratic

residues of N, each prime factor of N is discovered to have certain numbers

(usually primes) as quadratic residues. This implies that the prime factors of N

lie in readily determined arithmetic sequences. By combining these, a sequence of

trial divisors can be generated.

This method [38, 75, p. 198] was used by Jerry Johnson in 1963 to factor

N = 2101 􀀀 1, a number which had stood for decades as the Mersenne number

whose factorization was \most wanted". In the IBM 704 program that factored it,

prime quadratic residues of N were obtained from the continued fraction expansion

of

p

mN for various values of m. (See [32] for a discussion of this method.) The

lvii III B 2 DEVELOPMENTS IN FACTORIZATION

program that expanded

p

mN and factored the denominators of the complete quotients

also checked to see if any of these denominators was a square, just as hand

calculators had done for decades. The occurrence of a square can sometimes give

an immediate factorization of N.

(c) Di_erence of Squares and Quadratic Forms. The di_erence of squares

method is one of the oldest factorization methods we have used. This method,

introduced by Fermat, was improved by Gauss [21, Sec. 319{321]. (See [42] for a

discussion of the use of this method on early sieves and [6] for its implementation

on an electronic computer, and see also [49, 50, 33, Ch. VI].) Fermat would seek

to _nd nontrivial x and y so that x2 􀀀 y2 = N, from which a factorization directly

follows. Gauss wrote this equation as the congruence y2 _ x2 􀀀 N (mod E) for

various moduli E, thereby restricting the values of x to about one half of the possible

residues modulo E. Combining these restrictions produced a sieve which excluded

all values of x except for about one in 2s when s exclusion moduli E were used.

For some numbers with a special form such as 2n 􀀀 1, the x in this representation

can be shown to lie in a certain arithmetic sequence. When this information is

introduced at the outset as a change of variable, the sifting problem is considerably

reduced [45, 50].

Since the di_erence of squares method works best when N can be expressed as

a product of two factors of comparable size, it is sometimes better to factor mN,

instead of N, for some value of m. (See [39] for a discussion of this old idea.) One

then seeks values for x and y so that y2 _ x2 􀀀 mN (mod E), again for various

values of E. A sieve on x is then set up as before.

This method was used on all the sieve machines of DHL, one of the most

impressive results being the DLS 127 factorization

2136 + 1

257:383521

= 2368179743873:373200722470799764577

[7, p. 644]. This problem was run on a standby basis on that sieve for 2600 hours

before the number factored. Ten di_erent multipliers m were used, the last, which

did the job, being

m10 = 165670849 = 1 + 26:32:7:17:2417 :

The sieve was run for only 12.5 hours with m10. This sobering result shows all too

well how little we knew (and still know) about choosing a good multiplier in this

method.

In addition to the special case of a di_erence of squares, there is also Euler's

factorization method of expressing N as a quadratic form in two di_erent ways.

This method was employed on the di_erent sieves to good e_ect [68, 48, p. 106].

A still further method, using sets of forms, was developed in [65]. Generally speaking,

however, sieve methods of factorization no longer compete with the continued

fraction method. (See also [48].)

(d) The Continued Fraction Method. Experience with Legendre's method and

an analysis of its arithmetical behavior suggested to JB that certain residues produced

in the simple continued fraction expansion of

p

mN might be multiplied together

to produce a perfect square. This procedure (incorrectly called \Legendre's

Method" in the _rst edition (1969) of [32]) contrasts with method (b) above, in

III B 2 DEVELOPMENTS IN FACTORIZATION lviii

which a square times a prime is sought. Although previous hand calculation with

this method had shown that a square produced in this way quite often failed to

lead to a factorization of N, it became apparent when this method was running

at UCLA that it was, despite these failures, very much more powerful than any

general factoring method that had been used before [75].

The ideas in this method had been discussed earlier from the point of view

of the failures in the method by DHL and R. E. Powers [46], because as a hand

method it continually failed to factor N despite a large amount of computation.

As the method was developed by Mike Morrison and JB, it also became apparent

that a small set of primes was all that was needed in factoring the denominators

of the complete quotients; most of the denominators were discarded when they did

not factor enough with just these primes. This has been veri_ed in general through

the statistics that have been kept in recent years by Marvin Wunderlich. In private

conversations, H. J. Godwin has also indicated that in his experience with the

method, a small set of primes augmented by new primes that arise from completely

factoring some of the denominators, seems to provide a growing factor base which

is quite e_ective for the method.

Although the method often fails to factor N the _rst time that a square has

been constructed, it almost always factors the number soon after the squares begin

to appear. The power of the method can be illustrated by the factorization of 2128+1

[73], that of 2149 􀀀 1 by Rich Schroeppel [7, p. 645], that of the 49-digit cofactor

of 3121 􀀀 1 by SSW, and by the fact that throughout these tables no composite

number with 50 or fewer digits remains to be factored. (See IV for more recent

information.) The main reason for this power is that all the auxiliary factoring is

of numbers less than 2

p

mN.

(e) The Methods of John Pollard. Two other methods, introduced by John

Pollard, were of great importance in carrying out the factorizations in these tables.

The _rst, or \p �� 1" method [80] is often spectacularly successful since it can

sometimes _nd a quite enormous factor p with very little computing if p 􀀀 1 splits

entirely or almost entirely into a product of small primes.

The p 􀀀 1 method may have one or two steps. Using only the _rst step, one

_nds a factor p, regardless of its size, if p 􀀀 1 is a product of small primes. Using

both steps, one _nds a factor p if p 􀀀 1 is a product of small primes and a single

larger prime.

Both the single and double step methods have been programmed and have

occasionally produced much larger factors than those which can be found by most

other methods. For example, using only the single step method, we found the 19-

digit factor p = 1325815267337711173 of 1053 􀀀 1 in only a few minutes on the

IBM 360/67, since p 􀀀 1 = 22:32:11:53:1279:1553:3557:8941. Robert Baillie at the

University of Illinois used the double step method to _nd the impressive 25-digit

factor p = 1155685395246619182673033 of the 63-digit cofactor of the Mersenne

number 2257􀀀1 in about 50 minutes on the Plato system's CDC 6500, since p􀀀1 =

23:32:192:47:67:257:439:119173:1050151. It was fortunate that the _rst step was

taken at least up to 119173, for otherwise this factor of 2257 􀀀 1 would not have

been found. He has kindly permitted us to publish other factors he has found by

this method.

A related method which can _nd prime factors p of N when p + 1 factors

completely into small primes, has been programmed by Earl Ecklund and JB at

lix III B 3(a) THE THEORY

DeKalb. The two step method for p 􀀀 1 and p + 1 has been programmed by Hugh

Williams at Winnipeg. In this modi_cation of Pollard's method the divisibility

properties of Lucas sequences are used. The factors found by Williams are included

here with his permission (two factors were found independently by G. J. Stevens).

It sometimes happens in this method that the smallest factor is not the _rst

to be found. For example, the impressive 23-digit factor 53199025841281128499153

is the largest factor of 1159 + 1, and this was discovered before the two 17-digit

factors.

The second method of Pollard [81], the so-called \Rho" or \Monte Carlo"

method, has been used by the authors only in auxiliary factoring associated with

primality testing. This powerful method was also used by M. Penk [77] to discover

the factor 535006138814359 of 2257􀀀1, the largest of the originalMersenne numbers

and known to be composite for half a century. Richard Brent also used a variation

of this method to factor the eighth Fermat number F8 = 2256 + 1, obtaining the

factor 1238926361552897. The cofactor of F8 was shown to be prime by Williams

and Brent.

The factorization of 2191 􀀀1 is interesting in that it was accomplished through

the use of four di_erent factoring methods: besides the \Euler factor" 383, the

second factor was then found by direct search; the fourth was found by Pollard

p 􀀀 1; the third and _fth were found using the continued fraction method. (The

second factor could actually have been found much more readily using the Pollard

p 􀀀 1 method.)

There is little doubt that Pollard's methods will have great importance in

further factorizations in these tables, since most composite numbers in these tables

have not yet been attacked by either of these methods. (This work was done by

the time of the second edition. See Section IV A 2(a).)

Навигация