Two Sieves

Carl Pomerance

(This paper is dedicated to the memory of my friend and

teacher, Paul Erdos)

I

t is the best of times for the game of fac- was largely ignored, since it was considered triv-

toring large numbers into their prime fac- ial. After all, it was doable in principle, so what

tors. In 1970 it was barely possible to fac- else was there to discuss? A few researchers ig-

tor “hard” 20-digit numbers. In 1980, in nored the fashions of the time and continued to

the heyday of the Brillhart-Morrison con- try to find fast ways to factor. To these few it

tinued fraction factoring algorithm, factoring of was a basic and fundamental problem, one that

50-digit numbers was becoming commonplace. should not be shunted to the side.

In 1990 my own quadratic sieve factoring algo- But times change. In the last few decades we

rithm had doubled the length of the numbers have seen the advent of accessible and fast com-

that could be factored, the record having 116 dig- puting power, and we have seen the rise of cryp-

its. tographic systems that base their security on our

By 1994 the quadratic sieve had factored the supposed inability to factor quickly (and on

famous 129-digit RSA challenge number that other number theoretic problems). Today there

had been estimated in Martin Gardner™s 1976 Sci- are many people interested in factoring, recog-

entific American column to be safe for 40 nizing it not only as a benchmark for the secu-

quadrillion years (though other estimates around rity of cryptographic systems, but for comput-

then were more modest). But the quadratic sieve ing itself. In 1984 the Association for Computing

is no longer the champion. It was replaced by Machinery presented a plaque to the Institute for

Pollard™s number field sieve in the spring of Electrical and Electronics Engineers (IEEE) on

1996, when that method successfully split a the occasion of the IEEE centennial. It was in-

130-digit RSA challenge number in about 15% of scribed with the prime factorization of the num-

the time the quadratic sieve would have taken. ber 2251 ’ 1 that was completed that year with

In this article we shall briefly meet these fac- the quadratic sieve. The president of the ACM

torization algorithms”these two sieves”and made the following remarks:

some of the many people who helped to de-

About 300 years ago the French

velop them.

mathematician Mersenne speculated

In the middle part of this century, computa-

that 2251 ’ 1 was a composite, that

tional issues seemed to be out of fashion. In most

is, a factorable number. About 100

books the problem of factoring big numbers

years ago it was proved to be fac-

torable, but even 20 years ago the

computational load to factor the

Carl Pomerance is research professor of mathematics

number was considered insur-

at the University of Georgia, Athens, GA. His e-mail ad-

mountable. Indeed, using conven-

dress is carl@ada.math.uga.edu.

tional machines and traditional

Supported in part by National Science Foundation grant

search algorithms, the search time

number DMS-9206784.

DECEMBER 1996 NOTICES AMS 1473

OF THE

was estimated to be about 1020 years. I had wasted too much time, and I missed the

problem.

The number was factored in Febru-

So can you find the clever way? If you wish

ary of this year at Sandia on a Cray

to think about this for a moment, delay reading

computer in 32 hours, a world

the next paragraph.

record. We™ve come a long way in

computing, and to commemorate

Fermat and Kraitchik

IEEE™s contribution to computing we

The trick is to write 8051 as 8100 ’ 49, which

have inscribed the five factors of the

is 902 ’ 72 , so we may use algebra, namely, fac-

Mersenne composite on a plaque.

toring a difference of squares, to factor 8051. It

Happy Birthday, IEEE.

is 83 — 97 .

Does this always work? In fact, every odd

Factoring big numbers is a strange kind of

composite can be factored as a difference of

mathematics that closely resembles the experi-

2

squares: just use the identity ab = 1 (a + b)

mental sciences, where nature has the last and

2

2

’ 1 (a ’ b) . Trying to find a pair of squares

definitive word. If some method to factor n runs

2

for awhile and ends with the statement “ d is a which work is, in fact, a factorization method of

factor of n”, then this assertion may be easily Fermat. Just like trial division, which has some

checked; that is, the integers have the last and very easy cases (such as when there is a small

definitive word. One can thus get by quite nicely prime factor), so too does the difference-of-

without proving a theorem that a method works squares method have easy cases. For example, √

in general. But, as with the experimental sci- if n = ab where a and b are very close to n,

ences, both rigorous and heuristic analyses can as in the case of n = 8051, it is easy to find the

be valuable in understanding the subject and two squares. But in its worst cases, the differ-

moving it forward. And, as with the experimen- ence-of-squares method can be far worse than

tal sciences, there is sometimes a tension be- trial division. It is worse in another way too.

tween pure and applied practitioners. It is held With trial division, most numbers fall into the

by some that the theoretical study of factoring easy case; namely, most numbers have a small

is a freeloader at the table (or as Hendrik Lenstra factor. But with the difference-of-squares

once colorfully put it, paraphrasing Siegel, “a pig method, only a small fraction of numbers have

in the rose garden”), enjoying undeserved at- a divisor near their square root, so the method

tention by vapidly giving various algorithms la- works well on only a small fraction of possible

bels, be they “polynomial”, “exponential”, “ran- inputs. (Though trial division allows one to begin

dom”, etc., and offering little or nothing in return a factorization for most inputs, finishing with a

to those hard workers who would seriously com- complete factorization is usually far more dif-

pute. There is an element of truth to this view. ficult. Most numbers resist this, even when a

But as we shall see, theory played a significant combination of trial division and difference-of-

role in the development of the title™s two sieves. squares is used.)

In the 1920s Maurice Kraitchik came up with

A Contest Problem an interesting enhancement of Fermat™s differ-

But let us begin at the beginning, at least my be- ence-of-squares technique, and it is this en-

ginning. When I give talks on factoring, I often hancement that is at the basis of most modern

repeat an incident that happened to me long factoring algorithms. (The idea had roots in the

ago in high school. I was involved in a math con- work of Gauss and Seelhoff, but it was Kraitchik

test, and one of the problems was to factor the who brought it out of the shadows, introducing

number 8051. A time limit of five minutes was it to a new generation in a new century. For

given. It is not that we were not allowed to use more on the early history of factoring, see [23].)

pocket calculators; they did not exist in 1960, Instead of trying to find integers u and v with

u2 ’ v 2 equal to n, Kraitchik reasoned that it

around when this event occurred! Well, I was

might suffice to find u and v with u2 ’ v 2 equal

fairly good at arithmetic, and I was sure I could

to a multiple of n, that is, u2 ≡ v 2 mod n. Such

trial divide up to the square root of 8051 (about

90) in the time allowed. But on any test, espe- a congruence can have uninteresting solutions,

those where u ≡ ±v mod n, and interesting so-

cially a contest, many students try to get into the

lutions, where u ≡ ±v mod n. In fact, if n is odd

mind of the person who made it up. Surely they

would not give a problem where the only rea- and divisible by at least two different primes,

sonable approach was to try possible divisors then at least half of the solutions to

u2 ≡ v 2 mod n, with uv coprime to n, are of the

frantically until one was found. There must be

a clever alternate route to the answer. So I spent interesting variety. And for an interesting solu-

tion u, v , the greatest common factor of u ’ v

a couple of minutes looking for the clever way,

and n, denoted (u ’ v, n), must be a nontrivial

but grew worried that I was wasting too much

factor of n. Indeed, n divides u2 ’ v 2 =

time. I then belatedly started trial division, but

1474 NOTICES AMS VOLUME 43, NUMBER 12

OF THE

(u ’ v)(u + v) but divides neither factor. So n Lehmer and R. E. Powers suggested replacing

must be somehow split between u ’ v and u + v. Kraitchik™s function Q(x) = x2 ’ n with another

As an aside, it should be remarked that find- that is derived from the continued-fraction ex-

√

ing the greatest common divisor (a, b) of two pansion of n.

given numbers a and b is a very easy task. If If ai /bi is the i-th continued fraction con-

√

0 < a ¤ b and if a divides b, then (a, b) = a. If 2 2

n , let Qi = ai ’ bi n. Then

vergent to

a does not divide b, with b leaving a remainder 2

Qi ≡ ai mod n. Thus, instead of playing with the

r when divided by a, then (a, b) = (a, r ). This

numbers Q(x), we may play with the numbers

neat idea of replacing a larger problem with a

Qi , since in both cases they are congruent mod-

smaller one is over two thousand years old and

ulo n to known squares. Although continued

is due to Euclid. It is very fast: it takes about as

fractions can be ornery beasts as far as compu-

much time for a computer to find the greatest

tation goes, the case for quadratic irrationals is

common divisor of a and b as it would take to

quite pleasant. In fact, there is a simple iterative

multiply them together.

procedure (see [16]) going back to Gauss and per-

Let us see how Kraitchik might have factored

haps earlier for computing what is needed here,

n = 2041 . The first square above n is

462 = 2116. Consider the sequence of numbers namely, the sequence of integers Qi and the

Q(x) = x2 ’ n for x = 46, 47, . . .. We get residues ai mod n.

But why mess up a perfectly simple quadratic

75, 168, 263, 360, 459, 560, . . . .

polynomial with something as exotic as contin-

So far no squares have appeared, so Fermat ued fractions? It is because of the inequality

√

|Qi | < 2 n. The numbers Qi are smaller in ab-

might still be searching. But Kraitchik has an-

other option: namely, he tries to find several solute value than the numbers Q(x). (As x moves

√

numbers x with the product of the corre- away from n , the numbers Q(x) grow ap-

√

sponding numbers Q(x) equal to a square. For proximately linearly, with a slope of 2 n.) If

if Q(x1 ) · · · Q(xk ) = v 2 and x1 · · · xk = u, then one wishes to “play” with numbers to find some

of them with product a square, it is presumably

u2 = x2 · · · x2 ≡ (x2 ’ n) · · · (x2 ’ n)

1 1

k k

easier to do this with smaller numbers than with

= Q(x1 ) · · · Q(xk ) = v 2 mod n; larger numbers. So the continued fraction of

Lehmer and Powers has an apparent advantage

that is, we have found a solution to

u2 ≡ v 2 mod n . But how to find the set over the quadratic polynomial of Kraitchik.

x1 , . . . , xk ? Kraitchik notices that some of the

How to “Play” with Numbers

numbers Q(x) factor very easily:

It is certainly odd to have an instruction in an

75 = 3 — 52 , 168 = 23 — 3 — 7, algorithm asking you to play with some numbers

360 = 23 — 32 — 5, 560 = 24 — 5 — 7. to find a subset with product a square. I am re-

minded of the cartoon with two white-coated sci-

From these factorizations he can tell that the

entists standing at a blackboard filled with ar-

product of these four numbers is

cane notation, and one points to a particularly

210 — 34 — 54 — 72 , a square! Thus he has

delicate juncture and says to the other that at

u2 ≡ v 2 mod n, where

this point a miracle occurs. Is it a miracle that

u = 46 · 47 · 49 · 51 ≡ 311 mod 2041, we were able to find the numbers 75, 168, 360,

and 560 in Kraitchik™s sequence with product a

v = 25 · 32 · 52 · 7 ≡ 1416 mod 2041.

square? Why should we expect to find such a sub-

He is now nearly done, since sequence, and, if it exists, how can we find it ef-

311 ≡ ±1416 mod 2041. Using Euclid™s algo- ficiently?

rithm to compute the greatest common factor A systematic strategy for finding a subse-

(1416 ’ 311, 2041), he finds that this is 13, and quence of a given sequence with product a square

so 2041 = 13 — 157.

was found by John Brillhart and Michael Morri-

son, and, surprisingly, it is at heart only linear

Continued Fractions

algebra (see [16]). Every positive integer m has

The essence of Kraitchik™s method is to “play”

an exponent vector v(m) that is based on the

with the sequence x2 ’ n as x runs through in-

√ prime factorization of m. Let pi denote the i-th

tegers near n to find a subsequence with prod- v

prime, and say m = pi i . (The product is over

uct a square. If the square root of this square is

all primes, but only finitely many of the expo-

v and the product of the corresponding x val-

ues is u, then u2 ≡ v 2 mod n, and there is now nents vi are nonzero.) Then v(m) is the vector

(v1 , v2 , . . . ). For example, leaving off the infinite

a hope that this congruence is “interesting”,

namely, that u ≡ ±v mod n. In 1931 D. H. string of zeros after the fourth place, we have

DECEMBER 1996 NOTICES AMS 1475

OF THE

v(75) = (0, 1, 2, 0), are not negative. However, we can put an extra

v(168) = (3, 1, 0, 1), coordinate in each exponent vector, one that is

0 for positive numbers and 1 for negative num-

v(360) = (3, 2, 1, 0),

bers. (It is as if we are including the “prime” ’1

v(560) = (4, 0, 1, 1). in the factor base.) So allowing the auxiliary

numbers to be negative just increases the di-

For our purposes the exponent vectors give too

mension of the problem by 1.

much information. We are interested only in

For example, let us consider again the num-

squares, and since a positive integer m is a

ber 2041 and try to factor it via Kraitchik™s poly-

square if and only if every entry of v(m) is even,

nomial, but now allowing negative values. So

we should be reducing exponents modulo 2.

with Q(x) = x2 ’ 2041 and the factor base 2, 3,

Since v takes products to sums, we are looking

and 5, we have

for numbers such that the sum of their exponent

Q(43) = ’192 = ’26 · 3 ” (1, 0, 1, 0)

vectors is the zero vector mod 2. The mod 2 re-

Q(44) = ’105

ductions of the above exponent vectors are

’24 ” (1, 0, 0, 0)

Q(45) = ’16 =

v(75) ≡ (0, 1, 0, 0) mod 2,

75 = 3 · 52 ” (0, 0, 1, 0),

Q(46) =

v(168) ≡ (1, 1, 0, 1) mod 2,

where the first coordinates correspond to the ex-

v(360) ≡ (1, 0, 1, 0) mod 2,

ponent on ’1. So, using the smaller factor base

v(560) ≡ (0, 0, 1, 1) mod 2.

of 2, 3, and 5 but allowing also negatives, we are

especially lucky, since the three vectors assem-

Note that their sum is the zero vector! Thus the

bled so far are dependent. This leads to the con-

product of 75, 168, 360, and 560 is a square.

gruence (43 · 45 · 46)2 ≡ (’192)(’16) (75) mod

To systematize this procedure, Brillhart and

2041, or 12472 ≡ 4802 mod 2041. This again

Morrison suggest that we choose some number

gives us the divisor 13 of 2041, since

B and look only at those numbers in the se-

(1247 ’ 480, 2041) = 13.

quence that completely factor over the first B

Does the final greatest common divisor step

primes. So in the case above, we have B = 4. As

always lead to a nontrivial factorization? No it

soon as B + 1 such numbers have been assem-

does not. The reader is invited to try still another

bled, we have B + 1 vectors in the B-dimensional

assemblage of a square in connection with 2041.

B

vector space F2 . By linear algebra they must be

This one involves Q(x) for x = 41, 45, and 49

linearly dependent. But what is a linear depen-

and gives rise to the congruence

dence relation over the field F2? Since the only

6012 ≡ 14402 mod 2041. In our earlier termi-

scalars are 0 and 1, a linear dependence relation

nology, this congruence is uninteresting, since

is simply a subset sum equaling the 0-vector. And

601 ≡ ’1440 mod 2041. And sure enough, the

we have many algorithms from linear algebra

greatest common divisor (601 ’ 1440, 2041) is

that can help us find this dependency.

the quite uninteresting divisor 1.

Note that we were a little lucky here, since we

were able to find the dependency with just four

Smooth Numbers and the Stirrings of

vectors rather than the five vectors needed in the

Complexity Theory

worst case.

With the advent of the RSA public key cryp-

Brillhart and Morrison call the primes

tosystem in the late 1970s, it became particularly

p1 , p2 , . . . , pB the “factor base”. (To be more pre-

important to try to predict just how hard fac-

cise, they discard those primes pj for which n

toring is. Not only should we know the state of

is not congruent to a square, since such primes

the art at present, we would like to predict just

will never divide a number Qi in the continued-

what it would take to factor larger numbers be-

fraction method nor a number Q(x) in Kraitchik™s

yond what is feasible now. In particular, it seems

method.) How is B to be chosen? If it is chosen

empirically that dollar for dollar computers dou-

small, then we do not need to assemble too

ble their speed and capacity every one and a half

many numbers before we can stop. But if it is cho-

to two years. Assuming this and no new factor-

sen too small, the likelihood of finding a num-

ing algorithms, what will be the state of the art

ber in the sequence that completely factors over

in ten years?

the first B primes will be so minuscule that it

It is to this type of question that complexity

will be difficult to find even one number. Thus

theory is well suited. So how then might one an-

somewhere there is a happy balance, and with

alyze factoring via Kraitchik™s polynomial or the

factoring 2041 via Kraitchik™s method, the happy

Lehmer-Powers continued fraction? Richard

balance turned out to be B = 4.

Schroeppel, in unpublished correspondence in

Some of the auxiliary numbers may be nega-

the late 1970s, suggested a way. Essentially, he

tive. How do we handle their exponent vectors? begins by thinking of the numbers Qi in the con-

Clearly we cannot ignore the sign, since squares tinued-fraction method or the numbers Q(x) in

1476 NOTICES AMS VOLUME 43, NUMBER 12

OF THE

Kraitchik™s method as “random”. If you are pre- assemble the congruent squares we may be very

sented with a stream of truly random numbers unlucky and only come up with uninteresting so-

below a particular bound X, how long should you lutions which do not help in the factorization.

expect to wait before you find some subset with Again assuming randomness, we do not expect

product a square? inordinately long strings of bad luck, and this

Call a number Y-smooth if it has no prime fac- heuristic again supports the conjecture.

tor exceeding Y. (Thus a number which com- As mentioned, this complexity argument was

pletely factors over the primes up to pB is pB - first made by Richard Schroeppel in unpublished

smooth.) What is the probability that a random work in the late 1970s. (He assumed the result

positive integer up to X is Y-smooth? It is mentioned above from [4], even though at that

ψ(X, Y )/[X] ≈ ψ(X, Y )/X, where ψ(X, Y ) is the time it was not a theorem or even really a con-

number of Y-smooth numbers in the interval jecture.) Armed with the tools to study com-

[1, X]. Thus the expected number of random plexity, he used them during this time to come

numbers that must be examined to find just up with a new method that came to be known

one that is Y-smooth is the reciprocal of this as the linear sieve. It was the forerunner of the

probability, namely, X/ψ(X, Y ). But we must quadratic sieve and also its inspiration.

find about π (Y ) such Y-smooth numbers, where

Using Complexity to Come Up With a

π (Y ) denotes the number of primes up to Y. So

Better Algorithm: The Quadratic Sieve

the expected number of random numbers that

must be examined is about π (Y )X/ψ(X, Y ). And The above complexity sketch shows a place

how much work does it take to examine a num- where we might gain some improvement. It is the

ber to see if it is Y-smooth? If one uses trial di- time we are taking to recognize auxiliary num-

vision for this task, it takes about π (Y ) steps. bers that factor completely with the primes up

So the expected number of steps is to Y = pB, that is, the Y-smooth numbers. In the

π (Y )2 X/ψ(X, Y ). argument we assumed this is about π (Y ) steps,

It is now a job for analytic number theory to where π (Y ) is the number of primes up to Y. The

choose Y as a function of X so as to minimize probability that a number is Y-smooth is, ac-

the expression π (Y )2 X/ψ(X, Y ). In fact, in the cording to the notation above, ψ(X, Y )/[X]. As

late 1970s the tools did not quite exist to make you might expect and as is easily checked in

this estimation accurately. practice, when Y is a reasonable size and X is

This was remedied in a paper in 1983 (see [4]), very large, this probability is very, very small. So

though preprints of this paper were around for one after the other, the auxiliary numbers pop

several years before then. So what is the mini- up, and we have to invest all this time in each

mum? It occurs when Y is about one, only to find out almost always that the

exp( 1 log X log log X) and the minimum value number is not Y-smooth and is thus a number

2

is about exp(2 log X log log X). But what are “X” that we will discard.

and “ Y” anyway?1 The number X is an estimate It occurred to me early in 1981 that one might

for the typical auxiliary number the algorithm use something akin to the sieve of Eratosthenes

produces. In the continued-fraction method, X to quickly recognize the smooth values of

√

can be taken as 2 n. With Kraitchik™s polyno- Kraitchik™s quadratic polynomial Q(x) = x2 ’ n.

mial, X is a little larger: it is n1/2+µ . And the num- The sieve of Eratosthenes is the well-known de-

ber Y is an estimate for pB , the largest prime in vice for finding all the primes in an initial interval

the factor base. of the natural numbers. One circles the first

Thus factoring n, either via the Lehmer-Pow- prime 2 and then crosses off every second num-

ers continued fraction or via the Kraitchik poly- ber, namely, 4, 6, 8, etc. The next unmarked

nomial, should take about exp( 2 log n log log n) number is 3. It is circled, and we then cross off

steps. This is not a theorem; it is a conjecture. every third number. And so on. After reaching

The conjecture is supported by the above heuris- the square root of the upper limit of the sieve,

tic argument which assumes that the auxiliary one can stop the procedure and circle every re-

numbers generated by the continued fraction of

√ maining unmarked number. The circled numbers

n or by Kraitchik™s quadratic polynomial are are the primes; the crossed-off numbers the

“random” as far as the property of being

composites.

Y-smooth goes. This has not been proved. In ad-

It should be noted that the sieve of Eratos-

dition, getting many auxiliary numbers that are

thenes does more than find primes. Some

Y-smooth may not be sufficient for factoring n,

crossed-off numbers are crossed off many times.

since each time we use linear algebra over F2 to

For example, 30 is crossed off three times, as is

42, since these numbers have three prime fac-

tors. Thus we can quickly scan the array look-

1Actually, this is a question that has perplexed many

ing for numbers that are crossed off a lot and

a student in elementary algebra, not to mention many

so quickly find the numbers which have many

a philosopher of mathematics.

DECEMBER 1996 NOTICES AMS 1477

OF THE

Implementations and Enhancements

prime factors. And clearly there is a correlation

between having many prime factors and having In fact, I was very lucky that the quadratic sieve

all small prime factors. turned out to be a competitive algorithm. More

But we can do better than have a correlation. often than not, when one invents algorithms

By dividing by the prime, instead of crossing off, solely via complexity arguments and thought

numbers like 30 and 42 get transformed to the experiments, the result is likely to be too awk-

number 1 at the end of the sieve, since they are ward to be a competitive method. In addition,

completely factored by the primes used in the even if the basic idea is sound, there well could

sieve. So instead of sieving with the primes up be important enhancements waiting to be dis-

to the square root of the upper bound of the covered by the people who actually try the thing

sieve, say we only sieve with the primes up to out. This in fact happened with the quadratic

Y. And instead of crossing a number off, we di- sieve.

vide it by the prime. At the end of the sieve any The first person to try out the quadratic sieve

number that has been changed to the number 1 method on a big number was Joseph Gerver (see

is Y-smooth. But not every Y-smooth is caught [9]). Using the task as an opportunity to learn pro-

in this sieve. For example, 60 gets divided by its gramming, he successfully factored a 47-digit num-

prime factors and is changed to the number 2. ber from the Cunningham project. This project,

The problem is higher powers of the primes up begun early in this century by Lt.-Col. Allan J. Cun-

to Y. We can rectify this by also sieving by these ningham and H. J. Woodall, consists of factor-

higher powers and dividing hits by the under- ing into primes the numbers bn ± 1 for b up to

lying prime. Then the residual 1™s at the end 12 (and not a power) and n up to high numbers

correspond exactly to the Y-smooth numbers in (see [3]). Gerver™s number was a factor of

the interval. 3225 ’ 1.

The time for doing this is unbelievably fast Actually I had a hard time getting people to

compared with trial dividing each candidate try out the quadratic sieve. Many Cunningham

number to see if it is Y-smooth. If the length of project factorers seemed satisfied with the con-

the interval is N, the number of steps is only tinued-fraction method, and they thought that

about N log log Y, or about log log Y steps on the larger values of Kraitchik™s polynomial Q(x),

average per candidate. compared with the numbers Qi in the contin-

So we can quickly recognize Y-smooth num- ued-fraction method, was too great a handicap

bers in an initial interval. But can we use this idea for the fledgling quadratic sieve method. But at

to recognize Y-smooth values of the quadratic a conference in Winnipeg in the fall of 1982, I

polynomial Q(x) = x2 ’ n? What it takes for a convinced Gus Simmons and Tony Warnock of

sieve to work is that for each modulus m in the Sandia Laboratories to give it a try on their Cray

sieve, the multiples of the number m appear in computer.

regular places in the array. So take a prime p, Jim Davis and Diane Holdridge were assigned

for example, and ask, For which values of x do the task of coding up the quadratic sieve on the

we have Q(x) divisible by p? This is not a diffi- Sandia Cray. Not only did they succeed, but they

cult problem. If n (the number being factored) quickly began setting records. And Davis found

is a nonzero square modulo p, then there are two an important enhancement that mitigated the

residue classes a and b mod p such that handicap mentioned above. He found a way of

Q(x) ≡ 0 mod p if and only if x ≡ a or b mod switching to other quadratic polynomials after

values of the first one, Q(x) = x2 ’ n, grew un-

p. If n is not a square modulo p, then Q(x) is

never divisible by p and no further computations comfortably large. Though this idea did not sub-

with p need be done. stantially change the complexity estimate, it

So essentially the same idea can be used, and made the method much more practical. Their

we can recognize the Y-smooth values of Q(x) success not only made the cover of the Math-

in about log log Y steps per candidate value. ematical Intelligencer (the volume 6, number 3

What does the complexity argument give us? cover in 1984 had on it a Cray computer and the

The time to factor n is now about factorization of the number consisting of 71

√

exp( log n log log n); namely, the factor 2 in ones), but there was even a short article in Time

the exponent is missing. Is this a big deal? You magazine, complete with a photo of Simmons.

bet. This lower complexity and other friendly fea- It was ironic that shortly before the Sandia

tures of the method allowed a twofold increase team began this project, another Sandia team had

in the length of the numbers that could be fac- designed and manufactured an RSA chip for

tored (compared with the continued-fraction public key cryptography, whose security was

method discussed above). And so was born the based on our inability to factor numbers of

quadratic sieve method as a complexity argu- about 100 digits. Clearly this was not safe

enough, and the chip had to be scrapped.

ment and with no numerical experiments.

1478 NOTICES AMS VOLUME 43, NUMBER 12

OF THE

Around this time Peter Montgomery inde-

pendently came up with another, slightly better

way of changing polynomials, and we now use

his method rather than that of Davis.

One great advantage of the quadratic sieve

method over the continued-fraction method is

that with the quadratic sieve it is especially easy

to distribute the task of factoring to many com-

puters. For example, using multiple polynomi-

Photograph courtesy of the Computer Museum, Boston, MA.

als, each computer can be given its own set of

quadratic polynomials to sieve. At first, the great-

est successes of the quadratic sieve came from

supercomputers, such as the Cray XMP at San-

dia Laboratories. But with the proliferation of

low-cost workstations and PCs and the natural

way that the quadratic sieve can be distributed,

the records passed on to those who organized

distributed attacks on target numbers.

Robert Silverman was the first to factor a

number using many computers. Later, Red Al-

ford and I used over 100 very primitive, non-

networked PCs to factor a couple of 100-digit

numbers (see [2]). But we did not set a record,

Modern model of the Lehmer Bicycle Chain Sieve constructed

because while we were tooling up, Arjen Lenstra

by Robert Canepa and currently in storage at the Computer

and Mark Manasse [12] took the ultimate step in

Museum, 300 Congress Street, Boston, MA 02210.

distributing the problem. They put the quadratic

sieve on the Internet, soliciting computer time

number fields. His original idea was not for any

from people all over the world. It was via such

large composite, but for certain “pretty” com-

a shared effort that the 129-digit RSA challenge

posites that had the property that they were

number was eventually factored in 1994. This

close to powers and had certain other nice prop-

project, led by Derek Atkins, Michael Graff, Paul

erties as well. He illustrated the idea with a fac-

Leyland, and Lenstra, took about eight months 7

torization of the number 22 + 1, the seventh Fer-

of real time and involved over 1017 elementary

mat number. It is interesting that this number

steps.

was the first major success of the continued-frac-

The quadratic sieve is ultimately a very sim-

tion factoring method, almost twenty years ear-

ple algorithm, and this is one of its strengths.

lier.

Due to its simplicity one might think that it

I must admit that at first I was not too keen

could be possible to design a special-purpose

on Pollard™s method, since it seemed to be ap-

computer solely dedicated to factoring big num-

plicable to only a few numbers. However, some

bers. Jeff Smith and Sam Wagstaff at the Uni-

people were taking it seriously, one being Hen-

versity of Georgia had built a special-purpose

drik Lenstra. He improved some details in the al-

processor to implement the continued-fraction

gorithm and, along with his brother Arjen and

method. Dubbed the “Georgia Cracker”, it had

Mark Manasse, set about using the method to fac-

some limited success but was overshadowed by

tor several large numbers from the Cunning-

quadratic sieve factorizations on conventional

ham project. After a few successes (most notably

computers. Smith, Randy Tuler, and I (see [21])

a 138-digit number) and after Brian LaMacchia

thought we might build a special-purpose qua-

and Andrew Odlyzko had made some inroads in

dratic sieve processor. “Quasimodo”, for Qua-

dealing with the large, sparse matrices that come

dratic Sieve Motor, was built but never func-

up in the method, the Lenstras and Manasse set

tioned properly. The point later became moot 9

their eyes on a real prize, 22 + 1, the ninth Fer-

due to the exponential spread of low-cost, high-

mat number.2 Clearly it was beyond the range of

quality computers.

the quadratic sieve. Hendrik Lenstra™s own el-

liptic curve method, which he discovered early

The Dawn of the Number Field Sieve

Taking his inspiration from a discrete logarithm

algorithm of Don Coppersmith, Andrew Odlyzko, 2This number had already been suggested in Pollard™s

and Richard Schroeppel [6] that used quadratic original note as a worthy goal. It was known to be com-

number fields, John Pollard in 1988 circulated posite”in fact, we already knew a 7-digit prime factor”

a letter to several people outlining an idea of his but the remaining 148-digit cofactor was still compos-

for factoring certain big numbers via algebraic ite, with no factor known.

DECEMBER 1996 NOTICES AMS 1479

OF THE

the ring Z[±] consisting of all polynomial ex-

in 1985 and which is especially good at splitting

pressions in ± with integer coefficients. Since

numbers which have a relatively small prime

f (±) = 0 and f (m) ≡ 0 mod n, by substituting

factor (say, “only” 30 or so digits) had so far not

the residue m mod n for each occurrence of ±

been of help in factoring it. The Lenstras and

we have a natural map φ from Z[±] to Z/(nZ).

Manasse succeeded in getting the prime factor-

9

ization of 22 + 1 in the spring of 1990. This Our conditions on f, ±, and m ensure that φ is

well defined. And not only this, φ is a ring ho-

sensational achievement announced to the world

momorphism.

that Pollard™s number field sieve had arrived.

Suppose now that S is a finite set of coprime

But what of general numbers? In the summer

integer pairs a, b with two properties. The

of 1989 I was to give a talk at the meeting of the

first is that the product of the algebraic integers

Canadian Number Theory Association in Van-

a ’ ±b for all pairs a, b in S is a square in

couver. It was to be a survey talk on factoring,

Z[±], say, γ 2 . The second property for S is that

and I figured it would be a good idea to mention

the product of all the numbers a ’ mb for pairs

Pollard™s new method. On the plane on the way

a, b in S is a square in Z , say, v 2 . Since γ may

to the meeting I did a complexity analysis of the

be written as a polynomial expression in ±, we

method as to how it would work for general

may replace each occurrence of ± with the in-

numbers, assuming myriad technical difficul-

teger m, coming up with an integer u with

ties did not exist and that it was possible to run

φ(γ) ≡ u mod n. Then

it for general numbers. I was astounded. The «

complexity for this algorithm-that-did-not-yet-

u2 ≡ φ(γ)2 = φ(γ 2 ) = φ (a ’ ±b)

exist was of the shape exp(c(log n)1/3

(log log n)2/3 ). The key difference over the com- a,b ∈S

plexity of the quadratic sieve was that the most φ(a ’ ±b)

=

important quantity in the exponent, the power a,b ∈S

of log n, had its exponent reduced from 1/2 to

(a ’ mb) = v 2 mod n.

≡

1/3. If reducing the constant in the exponent had

a,b ∈S

such a profound impact in passing from the And we know what to do with u and v. Just as

continued-fraction method to the quadratic sieve, Kraitchik showed us seventy years ago, we hope

think what reducing the exponent in the expo- that we have an interesting congruence, that is,

nent might accomplish. Clearly this method de- u ≡ ±v mod n, and if so, we take the greatest

served some serious thought! common divisor (u ’ v, n) to get a nontrivial

I do not wish to give the impression that with factor of n.

this complexity analysis I had single-handedly Where is the set S of pairs a, b supposed

found a way to apply the number field sieve to to come from? For at least the second property

general composites. Far from it. I merely had a S is supposed to have, namely, that the prod-

shrouded glimpse of exciting possibilities for the uct of the numbers a ’ mb is a square, it is

future. That these possibilities were ever realized clear we might again use exponent vectors and

was mostly due to Joe Buhler, Hendrik Lenstra, a sieve. Here there are two variables a and b in-

and others. In addition, some months earlier stead of just the one variable in Q(x) in the qua-

Lenstra had done a complexity analysis for Pol- dratic sieve. So we view this as a parametrized

lard™s method applied to special numbers, and family of linear polynomials. We can fix b and

he too arrived at the expression exp(c(log n)1/3 let a run over an interval, then change to the next

(log log n)2/3 ). My own analysis was based on b and repeat.

some optimistic algebraic assumptions and on But S is to have a second property too: for

the same pairs a, b , the product of a ’ ±b is

arguments about what might be expected to

a square in Z[±]. It was Pollard™s thought that if

hold, via averaging arguments, for a general

we were in the nice situation that Z[±] is the full

number.

ring of algebraic integers in Q(±), if the ring is

The starting point of Pollard™s method to fac-

tor n is to come up with a monic polynomial f (x) a unique factorization domain, and if we know

over the integers that is irreducible and an in- a basis for the units, then we could equally well

teger m such that f (m) ≡ 0 mod n. The polyno- create exponent vectors for the algebraic inte-

gers a ’ ±b and essentially repeat the same al-

mial should have “moderate” degree d, meaning

gorithm. To arrange for both properties of S to

that if n has between 100 and 200 digits, then

d should be 5 or 6. For a number such as the hold simultaneously, well, this would just involve

9

ninth Fermat number, n = 22 + 1, it is easy to longer exponent vectors having coordinates for

come up with such a polynomial. Note that all the small prime numbers, for the sign of

8n = 2515 + 8 . So let f (x) = x5 + 8 , and let a ’ ±b, for all the “small” primes in Z[±], and

m = 2103 . for each unit in the unit basis.

Of what possible use could such a polynomial But how are we supposed to do this for a

be? Let ± be a complex root of f (x), and consider general number n? In fact, how do we even

1480 NOTICES AMS VOLUME 43, NUMBER 12

OF THE

uct of various algebraic integers a ’ ±b is a

achieve the first step of finding the polynomial

f (x) and the integer m with f (m) ≡ 0 mod n? square of an algebraic integer, then so too is the

And if we could find it, why should we expect corresponding product of norms a square of an

that Z[±] has all of the nice properties to make integer. Note too that we know how to find a set

Pollard™s plan work? of pairs a, b with the product of N(a ’ ±b) a

square. This could be done by using a sieve to

The Number Field Sieve Evolves discover Y-smooth values of N(a ’ ±b) and then

There is at the least a very simple device to get combine them via exponent vector algebra over

started, that is, to find f (x) and m. The trick is F2.

to find f (x) last. First, one decides on the degree But having the product of the numbers

d of f. Next, one lets m be the integer part of N(a ’ ±b) be a square, while a necessary con-

n1/d . Now write n in the base m, so that

dition for the product of the a ’ ±b to be a

n = md + cd’1 md’1 + · · · + c0 , where the base

square, is far from sufficient. The principal rea-

m “digits” ci satisfy 0 ¤ ci < m. (If n > (2d)d ,

son for this is that the norm map takes various

then the leading “digit” cd is 1.) The polynomial

prime ideals to the same thing in Z , and so the

f (x) is now staring us in the face; it is

norm can easily be a square without the argu-

xd + cd’1 xd’1 + · · · + c0 . So we have a monic

ment being a square. For example, the two de-

polynomial f (x), but is it irreducible?

gree one primes in Z[i] , 2 + i and 2 ’ i, have

There are many strategies for factoring prim-

norm 5. Their product is 5, which has norm

itive polynomials over Z into irreducible factors.

25 = 52 , but (2 + i)(2 ’ i) = 5 is squarefree. (Note

In fact, we have the celebrated polynomial-time

that if we are working in the ring of all algebraic

algorithm of Arjen Lenstra, Hendrik Lenstra,

integers in Q(±), then all of the prime ideal fac-

and Lászlo Lovász for factoring primitive poly-

tors of a ’ ±b for coprime integers a and b are

nomials in Z[x] (the running time is bounded by

degree one; namely, their norms are rational

a fixed power of the sum of the degree and the

primes.) For each prime p let Rp be the set of

number of digits in the coefficients). So suppose

solutions to f (x) ≡ 0 mod p . When we come

we are unlucky and the above procedure leads

across a pair a, b with p dividing N(a ’ ±b),

to a reducible polynomial f (x) , say,

then some prime ideal above p divides a ’ ±b.

f (x) = g(x)h(x). Then n = f (m) = g(m)h(m), and

from a result of John Brillhart, Michael Filaseta, And we can tell which one, since a/b will be con-

and Andrew Odlyzko this factorization of n is gruent modulo p to one of the members of Rp ,

nontrivial. But our goal is to find a nontrivial fac- and this will serve to distinguish the various

torization of n, so this is hardly unlucky at all! prime ideals above p. Thus we can arrange for

Since almost all polynomials are irreducible, it our exponent vectors to have #Rp coordinates

is much more likely that the construction will for each prime p and so keep track of the prime

let us get started with the number field sieve, ideal factorization of a ’ ±b. Note that #Rp ¤ d,

and we will not be able to factor n immediately. the degree of f (x).

There was still the main problem of how one So we have gotten over the principal hurdle,

might get around the fact that there is no rea-

but there are still many obstructions. We are

son to expect the ring Z[±] to have any nice prop-

supposed to be working in the ring Z[±], and this

erties at all. By 1990 Joe Buhler, Hendrik Lenstra,

may not be the full ring of algebraic integers. In

and I had worked out the remaining difficulties

fact, this ring may not be a Dedekind domain,

and, incorporating a very practical idea of Len

so we may not even have factorization into prime

Adleman [1], which simplified some of our

ideals. And even if we have factorization into

constructions,3 published a description of the

prime ideals, the above paragraph merely as-

general number field sieve in [11].

sures us that the principal ideal generated by the

Here is a brief summary of what we did. The

product of the algebraic integers a ’ ±b is the

norm N(a ’ ±b) (over Q ) of a ’ ±b is easily

square of some ideal, not necessarily the square

worked out to be bd f (a/b). This is the homog-

of a principal ideal. And even if it is the square

enized version of f. We define a ’ ±b to be

of a principal ideal, it may not be a square of an

Y-smooth if N(a ’ ±b) is Y-smooth. Since the

algebraic integer, because of units. (For example,

norm is multiplicative, it follows that if the prod-

the ideal generated by ’9 is the square of an

ideal in Z , but ’9 is not a square.) And even if

3Though Adleman™s ideas did not change our theoret-

the product of the numbers a ’ ±b is a square

ical complexity estimates for the running time, the sim-

plicities they introduced removed most remaining ob-

4It is a theorem that if f is a monic irreducible poly-

stacles to making the method competitive in practice

nomial over Z with a complex root ± and if γ is in the

with the quadratic sieve. It is interesting that Adleman

ring of integers of Q(±), then f (±)γ is in Z[±]. So if

himself, like most others around 1990, continued to

γ 2 is a square in the ring of integers of Q(±), then

think of the general number field sieve as purely a

f (±)2 γ 2 is a square in Z[±].

speculative method.

DECEMBER 1996 NOTICES AMS 1481

OF THE

tity in a factorization method such as the qua-

of an algebraic integer, how do we know it is the

square of an element of Z[±]? dratic sieve or the number field sieve is what I

The last obstruction is rather easily handled was calling “ X” earlier. It is an estimate for the

by using f (±)2 as a multiplier,4 but the other ob- size of the auxiliary numbers that we are hop-

structions seem difficult. However, there is a ing to combine into a square. Knowing X gives

simple and ingenious idea of Len Adleman [1] you the complexity; it is about

that in one fell swoop overcomes them all. The exp( 2 log X log log X) . In the quadratic sieve

we have X about n1/2+µ . But in the number field

point is that even though we are being faced with

some nasty obstructions, they form, modulo sieve, we may choose the polynomial f (x) and

squares, an F2-vector space of fairly small di- the integer m in such a way that

mension. So the first thought just might be to (a ’ mb)N(a ’ ±b) (the numbers that we hope

ignore the problem. But the dimension is not that to find smooth) is bounded by a value of X of

small. Adleman suggested randomly choosing the form exp(c (log n)2/3 (log log n)1/3 ). Thus the

some quadratic characters and using their val- number of digits of the auxiliary numbers that

ues at the numbers a ’ ±b to augment the ex- we sieve over for smooth values is about the 2/3

ponent vectors. (There is one fixed choice of the power of the number of digits of n, as opposed

random quadratic characters made at the start.) to the quadratic sieve where the auxiliary num-

So we are arranging for a product of numbers bers have more than half the number of digits

a ’ ±b to not only be a square up to the “ob- of n. That is why the number field sieve is

struction space” but also highly likely actually asymptotically so fast in comparison.

to be a square. For example, consider the above I mentioned earlier that the heuristic run-

problem with ’9 not being a square. If some- ning time for the number field sieve to factor n

how we cannot “see” the problem with the sign is of the form exp(c(log n)1/3 (log log n)2/3 ), but

but it sure looks like a square to us because we

I did not reveal what “ c” is. There are actually

know that for each prime p the exponent on p

three values of c depending on which version

in the prime factorization of ’9 is even, we

of the number field sieve is used. The “special”

might still detect the problem. Here is how: Con-

number field sieve, more akin to Pollard™s orig-

sider a quadratic character evaluated at ’9, in

inal method and well suited to factoring num-

this case the Legendre symbol (’9/p), which is 9

bers like 22 + 1 which are near high powers, has

1 if ’9 is a square mod p and ’1 if ’9 is not

c = (32/9)1/3 ≈ 1.523. The “general” number

a square mod p. Say we try this with p = 7 . It is

field sieve is the method I sketched in this paper

easy to compute this symbol, and it turns out

and is for use on any odd composite number that

to be ’1. So ’9 is not a square mod 7, and so

is not a power. It has c = (64/9)1/3 ≈ 1.923. Fi-

it cannot be a square in Z . If ’9 is a square mod

nally, Don Coppersmith [5] proposed a version

some prime p, however, this does not guaran-

of the general number field sieve in which many

tee it is a square in Z . For example, if we had

polynomials are used. The value of “ c” for this

√

tried this with 5 instead of 7, then ’9 would still

method is 1 (92 + 26 13)1/3 ≈ 1.902 . This

be looking like a square. Adleman™s idea is to 3

stands as the champion worst-case factoring

evaluate smooth values of a ’ ±b at the qua-

method asymptotically. It had been thought that

dratic characters that were chosen and use the

Coppersmith™s idea is completely impractical, but

linear algebra to create an element with two

[8] considers whether the idea of using several

properties: its (unaugmented) exponent vector

polynomials may have some practical merit.

has all even entries, and its value at each char-

acter is 1. This algebraic integer is highly likely,

The State of the Art

in a heuristic sense, to be a square. If it is not a

In April 1996 a large team (see [7]) finished the

square, we can continue to use linear algebra over

factorization of a 130-digit RSA challenge num-

F2 to create another candidate.

ber using the general number field sieve. Thus

To be sure, there are still difficulties. One of

the gauntlet has finally been passed from the

these is the “square root problem”. If you have

quadratic sieve, which had enjoyed champion

the prime factorizations of various rational in-

status since 1983 for the largest “hard” number

tegers and their product is a square, you can eas-

factored. Though the real time was about the

ily find the square root of the square via its

same as with the quadratic sieve factorization

prime factorization. But in Z[±] the problem

of the 129-digit challenge number two years ear-

does not seem so transparent. Nevertheless,

lier, it was estimated that the new factorization

there are devices for solving this too, though it

took only about 15% of the computer time. This

still remains as a computationally interesting

discrepancy was due to fewer computers being

step in the algorithm. The interested reader

used on the project and some “down time” while

should consult [15].

code for the final stages of the algorithm was

Perhaps it is not clear why the number field

being written.

sieve is a good factoring algorithm. A key quan-

1482 NOTICES AMS VOLUME 43, NUMBER 12

OF THE

The First Twenty Fermat Numbers

m

known factorization of Fm = 22 + 1

m

0 3

1 5

2 17

3 257

4 65537

641 · P7

5

274177 · P14

6

59649589127497217 · P22

7

1238926361552897 · P62

8

2424833 ·7455602825647884208337395736200454918783366342657 ·P99

9

45592577 ·6487031809 ·4659775785220018543264560743076778192897 ·P252

10

319489 ·974849 ·167988556341760475137 ·3560841906445833920513 ·P564

11

114689 ·26017793 ·63766529 ·190274191361 ·1256132134125569 ·C1187

12

2710954639361 ·2663848877152141313 ·3603109844542291969 ·319546020820551643220672513 ·C2391

13

14 C4933

1214251009 ·2327042503868417 ·C9840

15

825753601 ·C19720

16

31065037602817 ·C39444

17

13631489 ·C78906

18

70525124609 ·646730219521 ·C157804

19

In the table, the notation P k means a prime number of k decimal digits, while the notation C k means a composite

number of k decimal digits for which we know no nontrivial factorization.

The history of the factorization of Fermat numbers is a microcosm of the history of factoring. Fermat himself

m

knew about F0 through F4 , and he conjectured that all of the remaining numbers in the sequence 22 + 1 are prime.

However, Euler found the factorization of F5 . It is not too hard to find this factorization, if one uses the result, es-

sentially due to Fermat, that for p to be a prime factor of Fm it is necessary that p ≡ 1 mod 2m+2 , when m is at least

2. Thus the prime factors of F5 are all 1 mod 128, and the first such prime, which is not a smaller Fermat number,

is 641. It is via this idea that F6 was factored (by Landry in 1880) and that “small” prime factors of many other Fer-

mat numbers have been found, including more than 80 beyond this table.

The Fermat number F7 was the first success of the Brillhart-Morrison continued fraction factoring method. Brent

and Pollard used an adaptation of Pollard™s “rho” method to factor F8 . As discussed in the main article, F9 was fac-

tored by the number field sieve. The Fermat numbers F10 and F11 were factored by Brent using Lenstra™s elliptic

curve method.

We know that F14 , F20 and F22 are composite, but we do not know any prime factors of these numbers. That they

are composite was discovered via Pepin™s criterion: Fm is prime if and only if 3(Fm ’1)/2 ≡ ’1 mod Fm . The smallest

Fermat number for which we do not know if it is prime or composite is F24. It is now thought by many number the-

orists that every Fermat number after F4 is composite.

Fermat numbers are connected with an ancient problem of Euclid: for which n is it possible to construct a regu-

lar n-gon with straightedge and compass? Gauss showed that a regular n-gon is constructible if and only if n ≥ 3and

the largest odd factor of n is a product of distinct, prime Fermat numbers. Gauss™s theorem, discovered at the age

of 19, followed him to his death: a regular 17-gon is etched on his gravestone.

So where is the crossover between the qua- much memory a computer has. The quadratic

sieve is as well, but not to such a large degree.

dratic sieve and the number field sieve? The an-

There is much that was not said in this brief

swer to this depends somewhat on whom you

survey. An important omission is a discussion

talk to. One thing everyone agrees on: for smaller

of the algorithms and complexity of the linear

numbers”say, less than 100 digits”the qua-

algebra part of the quadratic sieve and the num-

dratic sieve is better, and for larger numbers”

ber field sieve. At the beginning we used Gauss-

say, more than 130 digits”the number field

ian elimination, as Brillhart and Morrison did with

sieve is better. One reason a question like this

the continued-fraction method. But the size of

does not have an easy answer is that the issue the problem has kept increasing. Nowadays a fac-

is highly dependent on fine points in the pro- tor base of size one million is in the ballpark for

gramming and on the kind of computers used. record factorizations. Clearly, a linear algebra

For example, as reported in [7], the performance problem that is one million by one million is not

of the number field sieve is sensitive to how a trifling matter. There is interesting new work

DECEMBER 1996 NOTICES AMS 1483

OF THE

on this that involves adapting iterative methods 18, 19, 20]. In addition, I am currently writing a

for dealing with sparse matrices over the real book with Richard Crandall, PRIMES: A compu-

numbers to sparse matrices over F2. For a recent tational perspective, that should be out sometime

reference, see [14]. in 1997.

Several variations on the basic idea of the I hope I have been able to communicate some

number field sieve show some promise. One can of the ideas and excitement behind the devel-

replace the linear expression a ’ mb used in opment of the quadratic sieve and the number

the number field sieve with bk g(a/b), where field sieve. This development saw an interplay

g(x) is an irreducible polynomial over Z of de- between theoretical complexity estimates and

gree k with g(m) ≡ 0 mod n. That is, we use two good programming intuition. And neither could

polynomials f (x), g(x) with a common root m have gotten us to where we are now without the

mod n (the original scenario has us take other.

g(x) = x ’ m). It is a subject of current research

Acknowledgments

to come up with good strategies for choosing

polynomials. Another variation on the usual This article is based on a lecture of the same title

number field sieve is to replace the polynomial given as part of the Pitcher Lecture Series at

f (x) with a family of polynomials along the lines Lehigh University, April 30“May 2, 1996. I grate-

suggested by Coppersmith. For a description of fully acknowledge their support and encour-

the number field sieve incorporating both of agement for the writing of this article. I also

these ideas, see [8]. thank the Notices editorial staff, especially Susan

The discrete logarithm problem (given a cyclic Landau, for their encouragement. I am grateful

group with generator g and an element h in the to the following individuals for their critical

group, find an integer x with g x = h) is also of comments: Joe Buhler, Scott Contini, Richard

keen interest in cryptography. As mentioned, Crandall, Bruce Dodson, Andrew Granville, Hen-

Pollard™s original idea for the number field sieve drik Lenstra, Kevin McCurley, Andrew Odlyzko,

was born out of a discrete logarithm algorithm. David Pomerance, Richard Schroeppel, John Sel-

We have come full circle, since Dan Gordon,

fridge, and Hugh Williams.

Oliver Schirokauer, and Len Adleman have all

given variations of the number field sieve that References

can be used to compute discrete logarithms in [1] L. M. Adelman, Factoring numbers using singu-

multiplicative groups of finite fields. For a recent lar integers, Proc. 23rd Annual ACM Sympos. The-

survey, see [22]. ory of Computing (STOC), 1991, pp. 64“71.

I have said nothing on the subject of primal- [2] W. R. Alford and C. Pomerance, Implementing

ity testing. It is generally much easier to recog- the self initializing quadratic sieve on a distributed

nize that a number is composite than to factor network, Number Theoretic and Algebraic Meth-

ods in Computer Science, Proc. Internat. Moscow

it. When we use complicated and time-consum-

Conf., June“July 1993 (A. J. van der Poorten, I. Sh-

ing factorization methods on a number, we al-

parlinski, and H. G. Zimmer, eds.), World Scien-

ready know from other tests that it is an odd

tific, 1995, pp. 163“174.

composite and it is not a power.

[3] J. Brillhart, D. H. Lehmer, J. L. Selfridge,

I have given scant mention of Hendrik

B. Tuckerman, and S. S. Wagstaff Jr., Factor-

Lenstra™s elliptic curve factorization method.

izations of bn ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12,

This algorithm is much superior to both the up to high powers, second ed., vol. 22, Contemp.

quadratic sieve and the number field sieve for Math., Amer. Math. Soc., Providence, RI, 1988.

all but a thin set of composites, the so-called [4] E. R. Canfield, P. Erdös, and C. Pomerance, On

“hard” numbers, for which we reserve the sieve a problem of Oppenheim concerning “Factorisa-

methods. tio Numerorum”, J. Number Theory 17 (1983),

There is also a rigorous side to factoring, 1“28.

where researchers try to dispense with heuris- [5] D. Coppersmith, Modifications to the number field

sieve, J. Cryptology 6 (1993), 169“180.

tics and prove theorems about factorization al-

[6] D. Coppersmith, A. M. Odlyzko, and R. Schroep-

gorithms. So far we have had much more suc-

pel, Discrete logarithms in GF(p), Algorithmica

cess proving theorems about probabilistic

1 (1986), 1“15.

methods than deterministic methods. We do not

[7] J. Cowie, B. Dodson, R. Marije Elkenbracht-

seem close to proving that various practical

Huizing, A. K. Lenstra, P. L. Montgomery, and

methods, such as the quadratic sieve and the

J. Zayer, A world wide number field sieve factor-

number field sieve, actually work as advertised. ing record: On to 512 bits, Advances in Cryptol-

It is fortunate that the numbers we are trying to ogy”Asiacrypt ˜96, to appear.

factor have not been informed of this lack of [8] M. Elkenbracht-Huizing, A multiple polynomial

proof! general number field sieve, Algorithmic Number

For further reading I suggest several of the ref- Theory, Second Intern. Sympos., ANTS-II, to ap-

erences already mentioned and also [10, 13, 17, pear.

1484 NOTICES AMS VOLUME 43, NUMBER 12

OF THE

[9] J. Gerver, Factoring large numbers with a qua-

dratic sieve, Math. Comp. 41 (1983), 287“294.

[10] A. K. Lenstra, Integer factoring, preprint.

[11] A. K. Lenstra and H. W. Lenstra Jr. (eds.), The

development of the number field sieve, Lecture

Notes in Math. vol. 1554, Springer-Verlag, Berlin

and Heidelberg, 1993.

[12] A. K. Lenstra and M. S. Manasse, Factoring by elec-

tronic mail, Advances in Cryptology”Eurocrypt

˜89 (J.-J. Quisquater and J. Vandewalle, eds.),

Springer-Verlag, Berlin and Heidelberg, 1990, pp.

355“371.

[13] H. W. Lenstra Jr., Elliptic curves and number the-

oretic algorithms, Proc. Internat. Congr. Math.,

Berkeley, CA, 1986, vol. 1 (A. M. Gleason, ed.),

Amer. Math. Soc., Providence, RI, 1987, pp. 99“120.

[14] P. L. Montgomery, A block Lanczos algorithm for

finding dependencies over GF(2), Advances in

Cryptology”Eurocrypt ˜95 (L. C. Guillou and J.-J.

Quisquater, eds.), Springer-Verlag, Berlin and Hei-

delberg, 1995, pp. 106“120.

[15] ” ”, Square roots of products of algebraic inte-

”

gers, Mathematics of Computation 1943“1993,

Fifty Years of Computational Mathematics (W.

Gautschi, ed.), Proc. Sympos. Appl. Math. vol. 48,

Amer. Math. Soc., Providence, RI, 1994, pp.

567“571.

[16] M. A. Morrison and J. Brillhart, A method of fac-

torization and the factorization of F7 , Math. Comp.

29 (1975), 183“205.

[17] A. M. Odlyzko, The future of integer factorization,

CryptoBytes (The technical newsletter of RSA Lab-

oratories) 1, no. 2 (1995), 5“12.

[18] C. Pomerance (ed.), Cryptology and computa-

tional number theory, Proc. Sympos. Appl. Math.

vol. 42, Amer. Math. Soc., Providence, RI, 1990.

[19] ” ” , The number field sieve, Mathematics of

”

Computation 1943“1993, Fifty Years of Compu-

tational Mathematics (W. Gautschi, ed.), Proc. Sym-

pos. Appl. Math. vol. 48, Amer. Math. Soc., Prov-

idence, RI, 1994, pp. 465“480.

[20] ” ”, On the role of smooth numbers in number

”

theoretic algorithms, Proc. Internat. Congr. Math.,

Zürich, Switzerland, 1994, vol. 1 (S. D. Chatterji,

ed.), Birkhaüser-Verlag, Basel, 1995, pp. 411“422.

[21] C. Pomerance, J. W. Smith, and R. Tuler, A pipe-

line architecture for factoring large integers with

the quadratic sieve algorithm, SIAM J. Comput. 17

(1988), 387“403.

[22] O. Schirokauer, D. Weber, and T. Denny, Discrete

logarithms: The effectiveness of the index calcu-

lus method, Algorithmic Number Theory, Second

Intern. Sympos., ANTS-II, to appear.

[23] H. C. Williams and J. O. Shallit, Factoring inte-

gers before computers, Mathematics of Compu-

tation 1943“1993, Fifty Years of Computational

Mathematics (W. Gautschi, ed.), Proc. Sympos.

Appl. Math. 48, Amer. Math. Soc., Providence, RI,

1994, pp. 481“531.

DECEMBER 1996 NOTICES AMS 1485

OF THE