A Tale of
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