Chapter 5

Factoring

The problem of distinguishing prime numbers from composite numbers and
of resolving the latter into their prime factors is known to be one of the most
C. F. Gauss5.1
important and useful in arithmetic.

5.1 Universal Exponent Method

The problem of primality testing covered in Chapter 4 is less di¬cult, in
general, than the topic of this chapter. We have already learned that public-key
cryptosystems such as RSA, base their security upon the presumed di¬culty of
integer factorization, a term that we now make precise.
x The Integer Factorization Problem (IFP)
Given n ∈ N ¬nd primes pj for j = 1, 2, . . . , r ∈ N with p1 < p2 < · · · < pr
e
r
such that n = j=1 pj j .
Essentially what the conclusion of the IFP says is the content of the Funda-
mental Theorem of Arithmetic (see Theorem C.6 on page 213). A subset of the
IFP (which is actually the same as the IFP in the case of an RSA modulus) is
the notion of splitting n ∈ N, by which we mean that we ¬nd r, s ∈ N such that
1 < r ¤ s < n and n = rs.
5.1 Carl Friederich Gauss (1777“1855) is perhaps the best-known and possibly the greatest
mathematician of all time. Evidence of his genius emerged at age three when he found an
error in his father™s bookkeeping. By age eight he had astonished his teacher, B¨ ttner, by
u
100
j with the simple observation that the ¬fty pairs (j + 1, 100 ’ j)
rapidly calculating j=1
for j = 0, 1, . . . , 49 each sum to 101 for a total of 5050. Ultimately, he entered the Collegium
Carolinum with funding from the Duke of Brunswick, to whom he dedicated his magnum opus
Disquisitiones Arithmeticae [95], published in 1801, from which the above quote was taken.
By 1795, he entered G¨ttingen University and received his doctorate at the age of twenty.
o
His accomplishments are too numerous to list here (see [164] for more of them), but it is safe
to say that his work continues to have in¬‚uence to this day. Gauss remained a professor at
G¨ttingen until he died in his sleep on February 23, 1855. His awareness over two centuries ago
o
of the importance of factoring methods was prescient given today™s applications to public-key
cryptography.


93
© 2003 by CRC Press LLC
94 5. Factoring

Of course, the oldest method of splitting n is trial division by which we

mean to divide n by all primes up to n. For n < 108 or so, this is not
unreasonable. However, since the running time of trial division can be shown to

be O(max(pr’1 , pr )) (see [123, p. 381] and [245, Theorem 2.3.1, p. 197]), then
we need more sophisticated methods since we already know that for long-term
security an RSA modulus should have 1024 bits. In fact, at the end of Section
3.2 when we were discussing RSA moduli, we promised the following method.
First, we need a new concept. For a given modulus n ∈ N, an exponent e ∈ N
is called a universal exponent if xe ≡ 1 (mod n) for all x ∈ N with gcd(x, n) = 1.
x Universal Exponent Factorization Method
Let e be a universal exponent for n ∈ N and set e = 2b m where b ≥ 0 and
m is odd. Execute the following steps.
(1) Choose a random base a such that 1 < a < n ’ 1. If gcd(a, n) > 1, then
we have a factor of n, and we may terminate the algorithm. Otherwise go
to step (2).
(2) Let x0 ≡ am (mod n). If x0 ≡ 1 (mod n), then go to step (1). Otherwise,
compute xj ≡ x2 (mod n) for all j = 1, . . . , b. If
j’1

xj ≡ ’1 (mod n),

then go to step (1). If

xj ≡ 1 (mod n), but xj’1 ≡ ±1 (mod n),

then gcd(xj’1 ’ 1, n) is a nontrivial factor of n so we may terminate the
algorithm.

If one compares the above with the Miller-Selfridge-Rabin probabilistic pri-
mality test in Section 4.4, striking similarities will be seen. However, the pri-
mality test is not guaranteed to have a value such that xj ≡ 1 (mod n) as we
have in the universal exponent method (due to the existence of the exponent e).
When n = pq is an RSA modulus, a universal exponent is sometimes taken
to be lcm(p ’ 1, q ’ 1) instead of φ(n) = (p ’ 1)(q ’ 1). Yet these two values
will be roughly the same since gcd(p ’ 1, q ’ 1) has an expectation of being
small when p and q are chosen arbitrarily. Furthermore, recalling the discussion
at the end of Section 3.2 on page 65, since de ’ 1 is a multiple of φ(n), then
de ’ 1 is a universal exponent, and the above method can be used to factor n
as alleged in Section 3.2. This is the major value of our universal exponent test
since actually ¬nding e is di¬cult in practice.

Example 5.1 Let n = 3763 and suppose that we know e = 3640 is a universal
exponent for n. Since e = 23 · 455, then we ¬rst choose a = 2 as a base
and compute 2455 ≡ 924 ≡ x0 (mod n). Then x1 ≡ 9242 ≡ 3338 (mod n),
and x2 ≡ 33382 ≡ 1 (mod n). Since x1 ≡ ±1 (mod n), then gcd(x1 ’ 1, n) =
gcd(3337, 3763) = 71 is a factor of n. Indeed n = 53 · 71.


© 2003 by CRC Press LLC
5.1. Universal Exponent Method 95

Exercises

5.1. If n = 2a+2 for a ∈ N, prove that 2a is a universal exponent modulo n.
a
k
5.2. Let n = 2a j=1 pj j , where a ≥ 0, aj ∈ N, and the pj s are distinct odd
primes. The following is called the Carmichael function (see page 82):
if n = 2a , and, 1 ¤ a ¤ 2,
φ(n)
2a’2 = φ(n)/2 if n = 2a , a > 2,
»(n) =
lcm(»(2a ), φ(pa1 ), . . . , φ(pak )) if k ≥ 1.
1 k
Prove that »(n) is a universal exponent for n.
5.3. Prove that for a given n ∈ N, »(n) is the minimal universal exponent for
n (see Exercise 5.2).
5.4. Prove that for any n ∈ N, »(n) φ(n).
In Exercises 5.5“5.13, use the universal exponent method to ¬nd a factor
of each given n assuming that the given e is a universal exponent modulo
n.
5.5. n = 15841 and e = 12960.
5.6. n = 46657 and e = 41472.
5.7. n = 107381 and e = 106572.
5.8. n = 2919533 and e = 2915328.
5.9. n = 14660479 and e = 14652760.
5.10. n = 32774813 and e = 1170120.
5.11. n = 47440937 and e = 447426.
5.12. n = 61429883 and e = 30707100.
5.13. n = 76859539 and e = 12807000.
5.14. Factor n = 4294967297 assuming that e = 33502080 is a universal expo-
nent. (Hint: The task will be made easier and more transparent in this
case if Exercise 4.4 on page 83 is employed.)
5.15. Use the technique of Exercise 5.14 to factor n = 18446744073709551617
with e = 72057331223781120.
””””””””””””
Suddenly Christopher Robin began to tell Pooh about some of the things
People called Kings and Queens and something called Factors....
from The House on Pooh Corner
by A. A. Milne (1882 “ 1956)




© 2003 by CRC Press LLC
96 5. Factoring

Pollard™s p ’ 1 Method
5.2
I could be bounded in a nut-shell, and count myself a king of in¬nite space,
were it not that I have bad dreams.
from Hamlet ” by Shakespeare

The algorithm presented herein can quickly ¬nd certain primes p dividing n
when we have that p ’ 1 has only “small” prime factors. In order to describe
the algorithm, we need the following notion.
De¬nition 5.2 (Smoothness)
If B, n ∈ N and n is divisible only by primes p ¤ B, then n is said to be
B-smooth and B is called a smoothness bound.

Given that deciding whether a given integer is composite or prime is easier
in general than factoring, we will assume that n has been checked and found
to be composite before applying any factoring algorithm. Moreover, we may
assume that we have checked that n is not a perfect power, for if n = me
where m, e ∈ N and e > 1, then we can actually determine m and e as follows.
For each prime p ¤ log2 n, do a binary search for r ∈ N satisfying n = rp ,
restricting attention to the range 2 ¤ r ¤ 2 (log2 n)/p +1 . This calculation may
be accomplished in O((log2 n)3 (log2 (log2 (log2 n)))) bit operations. Thus, this is
a reasonable pre-test for ensuring that we do not have such a power.
The following was known to the Lehmers in the 1930s, but they did not pub-
lish it since it was not useful with hand calculations, and they had no computer
on which to implement it. However, when it was discovered by Pollard [187] in
1974, the computational value of the technique came to light.
x Pollard™s p ’ 1 Factoring Method
We assume that n is known to be composite, but not a perfect power, in the
application of this algorithm, which attempts to split n.

(1) Select a random a ∈ Z/nZ, a ≥ 2, and if gcd(a, n) > 1, then terminate
the algorithm, since we have split n. Otherwise go to step (2).
(2) Select a smoothness bound B, let a1 = a, and set j = 2.
(3) Compute aj ≡ aj (mod n) using the repeated squaring method.
j’1

(4) Compute g = gcd(aj ’ 1, n).
(5) If g > 1, terminate the algorithm, since we have split n. If g = 1, or n, set
j = j + 1. If j ¤ B, go to step (3). Otherwise, terminate with “failure”.


Remark 5.3 The smoothness bound needs to be small enough to ensure that
the algorithm runs quickly, but large enough to ensure some reasonable chance

of success. Clearly we do not want to choose B anywhere near n or we will


© 2003 by CRC Press LLC
5.2. Pollard™s p ’ 1 Method 97

have no advantage over trial division. Also, we do not want it to be so small that
there is no hope of ¬nding a nontrivial factor. More precisely, since the running
time of Pollard™s method can be shown to be O((B ln B ln2 n + ln3 n) modular
multiplications, then for B = O(lnm n), for some ¬xed m ∈ N, the algorithm is
polynomial time. However, in this case, B is too small to ensure any reasonable
hope of success. Pollard™s method will ¬nd at least one out of every N primes
in time5.2 N 1+o(1) if n has N bits, where 2 ln2 N = ln B ln ln B. In practice a
bound for B is taken in the range 105 < B < 106 . If the algorithm ends in
failure, one variant is to look at some primes j > B and try steps (3)“(4) for
those values. There is also a second phase of Pollard™s p ’ 1 method that is
not included in a typical description of the method. The interested reader may
consult [196, p. 176] for details.

The Pollard method works when some prime factor p of n satis¬es the prop-
erty that p ’ 1 has only small factors since it is then likely that B! will be
divisible by p ’ 1. If so, then B! = (p ’ 1)m for some m ∈ N and since the
algorithm computes, ultimately, aB ≡ aB! (mod n), we know that

aB! ≡ (ap’1 )m ≡ 1 (mod p),

from Fermat™s Little Theorem. Thus, p gcd(aB ’ 1, n).
To thwart this method of attack on RSA, for example, one has to construct
primes for which the RSA modulus does not su¬er from this vulnerability. For
instance, if r is a large prime such that p = 2r + 1 is also prime, then the
RSA modulus will be resistant to the p ’ 1 attack. We will revisit this and
surrounding issues in Chapter 6 (see the discussion of strong primes on page
120).

Example 5.4 Let n = 8051 and select a = 29, B = 10. Then the values aj for
1 ¤ j ¤ 7 all satisfy gcd(aj ’ 1, n) = 1. However, a8 ≡ 61108 ≡ 7179 (mod n),
and gcd(7178, 8051) = 97. Indeed, n = 8051 = 83 · 97. Also, 96 = 25 · 3 is
B-smooth.

Example 5.5 Let n = 8549 and select a = 50, B = 17. Then the reader may
verify that for j = 1, 2, . . . , 16, gcd(aj ’ 1, n) = 1. However, gcd(6592, n) = 103
where a17 ≡ a17 ≡ 442617 ≡ 6593 (mod n). In fact, n = 103 · 83. Notice that
16
102 = 2 · 3 · 17 is B-smooth, but 82 = 2 · 41 is not so Pollard™s method achieved
the larger prime factor since it excels at getting those where p ’ 1 is B-smooth.

The p ’ 1 idea by Pollard has an analogue called the p + 1 factoring method
designed by Hugh Williams in [237], where the assumption is that there is a
prime factor p of n with p + 1 being B-smooth. Moreover, Pollard™s p ’ 1 idea
generalizes to the much more powerful elliptic curve algorithm about which we
will learn in Section 5.3.
5.2 The reader is reminded that f (n) = o(g(n)) means that limn’∞ f (n)/g(n) = 0. Thus,
o(1) is used to symbolize a function whose limit as n approaches in¬nity is 0.



© 2003 by CRC Press LLC
98 5. Factoring

Exercises
In Exercises 5.16“5.19, use Pollard™s p ’ 1 method to ¬nd a nontrivial factor
of the given n with the selected smoothness bound B and the value of a chosen
in each case.
5.16. n = 53203, B = 10, and a = 35.
5.17. n = 12091, B = 10, and a = 37.
5.18. n = 11663, B = 5, and a = 41.
5.19. n = 37151, B = 9, and a = 51.
° 5.20. The following is a version of Dixon™s algorithm, Dixon [76], which is based
upon Fermat™s di¬erence of squares method discussed on pages 89“90. The
goal is to ¬nd a nontrivial factor of a given composite n ∈ N.
We are given a set Sr = {p1 , p2 , . . . , pr } consisting of the ¬rst r primes,
which is called the factor base (see the discussion on page 43). Execute
the following steps with initial value i = 1.
(1) Randomly choose ai ∈ Z/nZ and compute bi ≡ a2 (mod n).
i
(2) Trial divide bi by the elements of Sr to determine if bi is pr -smooth.
If not, then discard it, and return to step (1) with the same value of
i. If it is, then save it as
r
e
pj i,j ,
bi =
j=1

set i = i + 1, and return to step (1) if i < r + 1. Otherwise go to step
(3).
(3) Select a subset T ⊆ {1, 2, . . . , r} such that

bi ≡ y 2 (mod n).
i∈T

If we set
x= ai ,
i∈T

then x2 ≡ y 2 (mod n). If x ≡ ±1 (mod n), then by Exercise 4.23 on
page 92, gcd(x ’ y, n) is a nontrivial factor of n.
Explain why such a subset T in step (3) must exist. (Hint: Determine a
means for the r-tuples (ei,1 , ei,2 , . . . , ei,r ) to be vectors over Z/2Z.)
5.21. Use Dixon™s method in Exercise 5.20 to ¬nd a nontrivial factor of n = 8549
using the factor base S4 = {2, 3, 5, 7}.
(Exercises 5.20“5.21 are a precursor to the topic to be studied in Section
5.4.)



© 2003 by CRC Press LLC
5.3. Lenstra™s Elliptic Curve Method 99

 Lenstra™s Elliptic Curve Method
5.3
Mathematics, rightly viewed, possesses not only truth, but supreme beauty ”
a beauty cold and austere, like that of sculpture.
Bertrand Russell (1872“1970)
British philosopher and mathematician

Knowledge of this optional section is is not necessary to move on to Section
5.4. This section is intended for the reader with prior knowledge of basic elliptic
curve theory such as that given in [165, Section 6.1, pp. 221“235]. While we
assume some such familiarity, we begin by summarizing the key facts about
elliptic curves that we will use.
q Elliptic Curve Facts
We assume that E(Q) is an elliptic curve over Q given by y 2 = x3 + ax + b
where a, b ∈ Z, and o denotes the point at in¬nity.
(1) (Addition of points): For any two points P = (x1 , y1 ) and Q = (x2 , y2 )
on E, with P, Q = o and P = ’Q, de¬ne

P + Q = (x3 , y3 ) = (m2 ’ x1 ’ x2 , m(x1 ’ x3 ) ’ y1 ), (5.6)

where
m1 /m2 = (y2 ’ y1 )/(x2 ’ x1 ) if P = Q,
m= (5.7)
m1 /m2 = (3x2 + a)/(2y1 ) if P = Q,
1

and

if P = o, for instance, then P + Q = Q for all points Q on E,

and
if P = ’Q, then P + Q = o.

(2) (Reduction modulo n): Let n > 1 be given and ¬xed with gcd(n, 6) = 1,
and gcd(4a3 +27b2 , n) = 1. Then we refer to E reduced modulo n when the
coe¬cients a, b are reduced modulo n, and each point P on E is reduced
modulo n in the following fashion. If P = (r1 /r2 , s1 /s2 ) where

gcd(r1 , r2 ) = gcd(s1 , s2 ) = gcd(r2 s2 , n) = 1,

then

P = (t1 , t2 ), where t1 ≡ r1 r2 (mod n) and t2 ≡ s1 s’1 (mod n),
’1
2

with r2 and s’1 being the multiplicative inverses of r2 and s2 modulo n,
’1
2
respectively (see Exercise 5.22). We denote the reduced curve by E(Z/nZ),
and if n is a prime, then this is a group.




© 2003 by CRC Press LLC
100 5. Factoring

(3) (Modular group law): Suppose that P1 , P2 are points on E(Q) where
P1 + P2 = o and the denominators of P1 , P2 are prime to n. Then P1 + P2
has coordinates having denominators prime to n if and only if there does
not exist a prime p n such that P1 + P2 = o (mod p) on the elliptic curve
E(Z/pZ).

Fact (3) above is the underlying key to the following algorithm.
In 1985, H. W. Lenstra5.3 discovered the elliptic curve method or ECM (see
[136]). The ECM is actually a generalization of Pollard™s p’1 method, studied in
Section 5.2, in the following sense. Pollard™s method relies upon the existence
of a prime divisor p of n, which has the property that p ’ 1 (the order of
(Z/pZ)— ) is B-smooth for a suitable bound B. If no such prime exists, then the
method fails. Suppose that instead of Z/pZ, we choose an elliptic curve group
over Z/pZ. Since it is known that the order, g, of such a group is of the form

p + 1 ’ t for some integer t with |t| < 2 p (see [165, Theorem 6.27, p. 237]),
then the selection of g being smooth, with respect to some bound B, will ¬nd a
nontrivial factor of n with high probability. If g is not B-smooth, then repeated
selection of a new elliptic curve group may succeed, an option not available with
the Pollard method.
x Lenstra™s Elliptic Curve Method (ECM)
In this algorithm, n ∈ N is assumed to be composite, prime to 6, and not a
perfect power (see the discussion on page 96), and r ∈ N is a parameter. The
goal is to split n.

(1) (Select and elliptic curve): Choose a random pair (E, P ) where E =
E(Z/nZ) is an elliptic curve:

y 2 = x3 + ax + b and P is a point on E.

Check that gcd(n, 4a3 + 27b2 ) = 1.5.4 If not, then we have split n if
1 < g < n, and we may terminate the algorithm. Otherwise, we select
another (E, P ) pair.
(2) (Choosing bounds): Select M ∈ N and bounds A, B ∈ N such that the
ap
canonical prime factorization for M is M = j=1 pj j for small primes
p1 < p2 < · · · < p ¤ B where apj = ln(A)/ ln(pj ) is the largest
a
exponent such that pj j ¤ A. Set j = k = 1.
5.3 Hendrik Willem Lenstra, Jr. (1949“) was born in Zaandam, the Netherlands. At the age
of twenty-eight, he was appointed full professor at the University of Amsterdam, where he
had obtained his doctorate under the direction of Frans Oort. By 1987, he was appointed as
full professor at UC Berkeley, where he currently resides. His considerable achievements are
re¬‚ected in his recognition including: the 1985 Fulkerton Prize; the 1995 honourary doctorate
from the Universit´ de Franche-Comt´, Besan¸on; and the 1995 honour as Kloosterman-
e e c
lecturer at the University of Leiden.
5.4 Recall that the discriminant of an elliptic curve cannot be 0 over the ¬eld of de¬nition, so

the gcd condition must hold over Z/nZ. The nonzero discriminant guarantees that the elliptic
curve has no multiple roots.



© 2003 by CRC Press LLC
5.3. Lenstra™s Elliptic Curve Method 101

(3) (Calculating multiple points):5.5 Using (5.6)“(5.7), compute pj P .
(4) (Computing the gcd):
(a) If pj P ≡ o (mod n), then set P = pj P , and reset k to k + 1.
(i) If k ¤ apj , then go to step (3).
(ii) If k > apj , then reset j to j + 1, and reset k to k = 1. If j ¤ ,
then go to step (3). Otherwise go to step (5).
(b) If pj P ≡ o (mod n), then compute gcd(m2 , n) for m2 in (5.7). If
n > g, terminate the algorithm, since we have split n. If g = n, go
to step (5).
(5) (Selecting a new pair): Set r = r ’1. If r > 0, go to step (1). Otherwise,
terminate with “failure”.

One of the beauties of the ECM is that its running time is highly reliant on
the factor, p n, found. Hence, one of the most useful means of employing the
ECM is for ¬nding “small” prime factors in a number n which is too large to
¬nd all its factors. The reasons behind this are as follows. Assuming that p is
the smallest prime dividing n, the expected running time of the ECM is known
(under certain plausible assumptions) to be

O(exp( (2 + o(1)) ln p(ln ln p)) · ln2 n).

This may be used in practice to select a smoothness bound B in step (2) of the
algorithm as:
B = exp( ln p(ln ln p)/2). (5.8)
Since we do not know p in advance, we may nevertheless select (for p) the value

n . In this case, it is estimated that one out of every B iterations will be
successful in splitting n.
The worst-case scenario for the ECM is when n is an RSA modulus, in which
case we have that the expected running time is:

O exp( (2 + o(1)) ln n(ln ln n) = O n (2+o(1))(ln ln n)/ ln n .

With this being said, it is not surprising that ECM is most successful at splitting
non-RSA moduli, usually ¬nding prime factors of less than 40 decimal digits in
large composite numbers. The current record is the ¬nding of a 47-digit prime in
a large composite number. Perhaps the most notable is the ¬nding, in 1995 by
Richard Brent, of a 40-digit prime dividing F10 , thereby leading to the complete
factoring of the tenth Fermat number (see page 81).
It is time for a very small example (of course, not realistic) to illustrate the
basic ideas behind the ECM.
5.5 Recently, Richard Schroeppel announced that halving as an elliptic curve operation on
points dramatically speeds up cryptographic operations such as key exchange, typically by a
factor of 2.4. Point halving was independently discovered by Knudsen [122].



© 2003 by CRC Press LLC
102 5. Factoring

Example 5.9 Let n = 923 and select (E, P ) = (y 2 = x3 + 2x + 9, (0, 3)). Then
gcd(4 · 23 + 27 · 92 , 923) = 1, so we choose B = 4, based upon (5.8), and let
A = 3, M = 6 = 2 · 3 = p1 · p2 . Now, using (5.6)“(5.7), with p1 = 2, we calculate

p1 P = 2(0, 3) ≡ (9’1 , ’82 · 27’1 ) ≡ (718, 373) ≡ o (mod n).

Thus we set P = (718, 373) and compute

p2 P = 3P ≡ 2P + P ≡ (505, 124) + (718, 373) ≡ o (mod n).

Thus, we have that a denominator in (5.7) is not prime to n. In fact, the
calculation of m for 4P + 2P yields m = (124 ’ 373)/(505 ’ 718) = 83/71, and
gcd(923, 71) = 71. Indeed, n = 13 · 71, and we have split n.

What Example 5.9 illustrates is that the failure of the existence of a modular
inverse for some m in the calculations may lead to a factor of n. Another way
of saying this is that the group law for multiplication actually fails in Z/nZ
since n is not prime and this allows us to get the factor. Indeed, it is somewhat
inaccurate in the ECM algorithm to say that pj P ≡ o (mod n), when in fact it
is pj P ≡ o (mod p) where p is he factor for which we were searching. However,
this is legitimate since we were, in a sense, assuming n to be prime and doing
the calculations as if it were so, in the hope that the calculations would “break
down” with an unde¬ned denominator for some value of m in (5.7).
Some concluding comments on complexity and the relationship between
ECM and the topic of Section 5.4 are in order. In the discussion, we will
be using, for the sake of convenience, the notation introduced in Appendix B
(see equation (B.5) on page 206).√ this notation, the expected running time
In
of ECM may be stated as Lp (1/2, 2) to ¬nd a factor p of n. Again, this shows,
as mentioned earlier, that the ECM depends very much on the size of the prime
factors of n so it will ¬nd the small ones ¬rst. In the case of an RSA modulus,
the expected running time of ECM may be stated as Lp (1/2, 1), and this is the
same as the (ordinary) quadratic sieve, a generalization of which we will study
in the next section. However, even the ordinary quadratic sieve is much more
e¬cient at factoring RSA moduli. The reason, as we will see, is that even the
ordinary quadratic sieve involves single precision operations, while elliptic curve
operations are more computationally intensive.
A summary of what we have learned thus far is this. Some algorithms operate
more e¬ciently on integers of a special form, such as Pollard™s p ’ 1 method.
Thus an overall strategy for splitting n would be to use trial division ¬rst, up to
some reasonable bound, then use Fermat™s di¬erence of squares method, after
which one could employ algorithms for small prime factors such as Pollard™s
p ’ 1 methods. Then the ECM can be used if such methods as p ’ 1 fail. When
all this fails to get a nontrivial factor, then we can bring out the bigger guns
such as the quadratic sieve or its stronger cousin, the multipolynomial quadratic
sieve, which is our next topic of study.




© 2003 by CRC Press LLC
5.3. Lenstra™s Elliptic Curve Method 103

Exercises

5.22. Show that P = (9/4, 29/8) is a point on the elliptic curve E(Q) given by
y 2 = x3 ’ x + 4. Find the reduction of P modulo 15.
5.23. If E(Z/nZ) is the elliptic curve over Z/nZ for n = 3749 given by y 2 =
x3 ’ 6x + 6 and P = (1, 1) on E, ¬nd 6P on E(Z/nZ).
5.24. Using the curve and the point in Exercise 5.23, ¬nd 6P if n = 4727.
5.25. Suppose that n > 1 and P is a point on the elliptic curve E(Z/nZ). Prove
that there exist j, k ∈ N such that jP = kP .
5.26. Prove that if n > 1 and there are j, k ∈ N with j ¤ k such that jP = kP
for a point P on the elliptic curve E(Z/nZ), then (k ’ j)P = o.5.6
5.27. With reference to Exercise 5.26, prove that if k is the order of P on
E(Z/nZ) and P = o, then k .
5.28. Suppose that for k ∈ N, kP = o for some point P on E(Z/nZ) where
n > 1. Furthermore, assume that

kP = o but (k/p)P = o for any prime divisor p of k. (5.10)

Prove that k is the order of P (see Exercise 5.26).5.7
In Exercises 5.29“5.34, use the elliptic curve and point in Example 5.9 to
factor the given n.
5.29. n = 3977.
5.30. n = 25973.
5.31. n = 17821.
5.32. n = 18323.
5.33. n = 38411.
5.34. n = 1884257.

smallest value r ∈ N such that rP = o is called the order of P . In general elliptic
5.6 The

curves, such points are called torsion points. (The value o is called the trivial torsion point.)
Thus, elliptic curve groups over ¬nite ¬elds consist only of torsion points. Such groups are
called torsion groups. A famous theorem by B. Mazur [155] says that if E is an elliptic curve
over Q, then the torsion subgroup of E(Q) is either Z/nZ for n ∈ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12}
or is of the form Z/2Z •Z/2nZ where n ∈ {1, 2, 3, 4}. For elliptic curves over arbitrary number
¬elds, this remains an open problem.
5.7 This is related to primality testing using elliptic curves. A result of Goldwasser and Killian

says that if there is prime divisor p of k with p > (n1/4 + 1)2 and there is a point satisfying
(5.10), then n is prime (see [101]). There are also elliptic curve cryptosystems, which we
will not study here. These cryptosystems are based upon the discrete log problem for elliptic
curves which is to ¬nd x ∈ Z such that P = xQ for a given P, Q ∈ E(F ), where E(F ) is an
elliptic curve over a ¬eld F . (See [165, Chapter 6, pp. 243“251].)



© 2003 by CRC Press LLC
104 5. Factoring

5.4 Multipolynomial Quadratic Sieve
The elliptic curve method is one of the fastest integer factorization methods
that is currently used in practice. The quadratic sieve algorithm seems to per-
form better on integers that are built up from two prime numbers of the same
order of magnitude; such integers are of interest in cryptography.
Hendrik Lenstra

We describe a generalization of the quadratic sieve method named in the ti-
tle. The ordinary quadratic sieve and its generalization go back to Seelho¬ [201]
in 1886, and was later used by Kraitchik [125] (see Footnote 4.4 on page 83) who
developed it further. Also, it was ¬rst analyzed and modernized by Pomerance
[188]. (For a further in-depth discussion of the history, see [239].) The version
that we study herein, using multiple polynomials, was independently proposed
in [66] and [167]. The idea is based at its foundation upon Fermat™s di¬erences
of squares method (see the discussion on pages 89“90).
That basic idea was developed by Dixon as seen in Exercise 5.20 on page 98.
With the ordinary quadratic sieve, in order to split n ∈ N, one looks at a
polynomial √
g(x) = (x + n )2 ’ n
for x ∈ (’n , n ). Then one builds a set of integers i ∈ T so that g(xi ) factors
over the factor base and

bi ≡ g(xi ) ≡ y 2 (mod n)
xi ∈T xi ∈T

as in the exercise. The problem, however, is that for a single choice of g(x),
there is an unreasonable amount of time required to generate a su¬ciently large
enough set T over which g(x) will factor. The reason is that for large n, the
interval (’n , n ) is also large since g(x) = O(n1/2+ ) is large as well, and so we
will probably not be able to factor most of the g(x) over a small set of primes.
The multipolynomial version solves this problem by establishing an e¬cient
means of using several polynomials so that the x values may be chosen from
smaller intervals rather than one large interval. This means that the average
polynomial values are smaller than the average of g and have a higher probability
of factoring over small primes than the g(x) values in the ordinary quadratic
sieve. This then is a way of running the ordinary quadratic sieve in parallel.
x Multipolynomial Quadratic Sieve (MPQS)
In this algorithm, n ∈ N is assumed to be a large composite number. The
goal is to split n.
(1) (Select bounds): Choose a large smoothness bound B and an M ∈ N

with ( 2n/M )1/4 > B.

(2) (Select a factor base): Choose a set of L ∈ N primes as a factor base




© 2003 by CRC Press LLC
5.4. Multipolynomial Quadratic Sieve 105

(see the discussion on page 43) that is ¬xed for the algorithm:5.8
n
F = {pi : pi is prime and = 1 for i = 1, 2, . . . , L},
pi
where the symbol is the Legendre symbol. For pi ∈ F with qi = pai < B,
i
compute solutions tqi to the congruences
t2i ≡ n (mod qi )
q

for 0 < tqi ¤ qi /2.
(3) (Create a quadratic polynomial): Choose
W (x) = a2 x2 + 2bx + c,
where a, b, c satisfy:

a2 ≈ 2n/M, 5.9 b2 ’ n = a2 c, |b| < a2 /2. (5.11)

(4) (Test W(x) for divisibility by factor base elements): If qi W (j) for
some j ∈ [’M, M ], called a sieve number, then qi (a2 j + b)2 ’ n, so

j ≡ a’2 (±tqi ’ b) (mod qi ),
since gcd(a, qi ) = 1 by Exercise 5.35. We compute a’2 (mod qi ) for all
such qi via:
’2 ’2 ’2
a’2 ≡ gi1 gi2 · · · gik (mod qi ).
Thus, for e¬ciency, with the calculation of g-primes by the methodology
in Exercise 5.35, we also compute and save, for i = 1, 2, . . . , r, all the
’2
numbers gi (mod qi ) for each qi = pai < B where pi ∈ F.
i

(5) (Sieving5.10 ): De¬ne a (2M + 1)-tuple:
s = (s(’M ), s(’M + 1), . . . , s(j), . . . , s(M )),
which we initialize by setting s(j) = 0 for all j ∈ [’M, M ]. For each sieve
number j ∈ [’M, M ], i.e., those for which some prime power qi = pai i
W (j), reset
s(j) = ln pi + s(j).5.11
5.8 One method of generating a factor base containing many small primes is to multiply n
by a suitable small integer m called a multiplier and factoring mn rather than n (see [191, p.
391]).
5.9 The symbol ≈ means approximately equals, and we will not de¬ne it more rigorously since

we will see in practice how it works. Moreover, it should be noted that the polynomial W (x)
plays the role of g(x) in Exercise 5.20. The reader may also go to Exercise 5.35 for an e¬cient
means of calculating such a, b, c.
5.10 In general with the MPQS, the amount of time spent on sieving takes more than 85% of

the total computing time.
5.11 An idea attributed to Schroeppel (see [32]) is that since W (j) is a quadratic polynomial,

∈ Z, whenever j is a sieve value. Thus we may e¬ciently calculate
qi W (j + qi ) for all
the sieve values.



© 2003 by CRC Press LLC
106 5. Factoring

5.12
(6) (Selection of factor candidates): De¬ne the report threshold to be

1
RT = ln M n/2 .
2

Select from step (5) all those values j for which s(j) ≈ RT , test W (j),
and save a, b, j, (and thus tacitly c via the choice in Exercise 5.35) only if
W (j) factors over F. If the number of W (j) selected is less than L + 2, go
to step (3). Otherwise, go to step (7).
(7) (Creation of exponent vector): Since we have L + 2 sieve values j, we
form:
L
bj
pi i , and bji ¤ ai , for j = 1, 2, . . . , L + 2
b j0
W (j) = (’1)
i=1

and associate with W (j) the exponent vector

vj = (bj0 , bj1 , . . . , bjL ) (mod 2),

so we have a binary L + 1-tuple for each j = 1, 2, . . . , L + 2. Since we have
L + 2 vectors with L + 1 coordinates, then there is at least one subset

T ⊆ {1, 2, . . . , L + 2}5.13

such that
vj ≡ 0 (mod 2),
j∈T
so
W (j) ≡ z 2 (mod n).
j∈T


(8) (Factor n): Since (a2 x + b)2 ≡ a2 W (x) (mod n), then

X2 ≡ (a2 j + b)2 ≡ z 2 a2 ≡ Y 2 (mod n),
j∈T j∈T

so if 1 < gcd(X ’ Y, n) < n, then we have a nontrivial factor of n.

There are many variations that will speed up the MPQS such as those found
in [32], which we will not discuss here. As noted in Section 5.3, the ECM should
be used in advance of the MPQS to ¬nd small prime factors of n, say up to
thirty decimal digits. When a number has smallest prime divisor larger than
thirty decimal digits, we use the MPQS. One big advantage of the MPQS over
report threshold is the average of ln |W (j)| for j ∈ [’M, M ]. When s(j) ≥ RT , W (j)
5.12 The

is a good candidate for factoring over the factor base.
5.13 We can use Gaussian elimination modulo 2 on the matrix whose columns are v to ¬nd a
j
set T. See Appendix C on page 222.



© 2003 by CRC Press LLC
5.4. Multipolynomial Quadratic Sieve 107

the ordinary quadratic sieve is that one can generate many a, b, c values, and
switch polynomials when the residues grow too large. In Exercise 5.35, we see
that if we have a ¬xed k and set of r g-primes, the number of polynomials which
may be calculated is
r r!
2k’1 = 2k’1 .
(r ’ k)!k!
k
As we have seen, residues from di¬erent polynomials can be merged later.
Thus the MPQS is suitable for parallel processing when each processor has its
own polynomials. The current factorization record for (the three-large-prime
variant of) the MPQS is a 135-digit number (which is actually a factor of the
Cunningham number 21606 + 1, see page 108) accomplished on August 29, 2001
by B. Dodson, A.K. Lenstra, P. Leyland, A. Mu¬et, and S. Wagsta¬. The
previous record was the factorization of RSA-129 (see Footnote 3.7 on page 63)
factored in 1994 (see [9] and Example 3.10 on page 63). In Section 5.5, we will
have a look at another powerhouse for factoring ” the number ¬eld sieve ”
which has supplanted the MPQS as the most widely used factoring algorithm.


Exercises

5.35. The following is an e¬cient means of calculating the a, b, c in the MPQS,
and hence of selecting the polynomials W (x). Choose r, k ∈ N with
1 < k < r.5.14 Generate primes g1 , g2 , . . . , gr , which are called g-primes,
satisfying:

(a) gi ≈ ( 2n/M )1/(2k) ,
n
(b) ( gi ) = 1, and
(c) for each i = 1, 2, . . . , r, gcd(gi , q) = 1 for all q ∈ F.
For some choice of k of the g-primes where 1 ¤ i1 < i2 < · · · < ik ¤ r, let
a = gi1 gi2 · · · gik .

Now, solve for bi with i = 1, 2, . . . , r in:
b2 ≡ n (mod gi ).
2
i

Then use the Chinese Remainder Theorem C.13 on page 215, to solve the
system of congruences, for a speci¬c choice of signs:
b ≡ ±bi1 (mod gi1 ); b ≡ ±bi2 (mod gi2 ); ··· b ≡ ±bik (mod gik ).
2 2 2


For this solution b, set c = (b2 ’ n)/a2 .
Show that the conditions in (5.11) are satis¬ed by this choice of a, b, c.
Then given n = 72452183, k = 2, r = 3, B = 5, M = 3, F = {2, 3}, and
g-primes 11, 17, determine a, b, c in this case.

5.14 In
this exercise, we will choose a small values of r for pedagogical purposes but in practice,
the MPQS typically uses a value such as r = 30, for instance.



© 2003 by CRC Press LLC
108 5. Factoring

 The Number Field Sieve
5.5
I have often admired the mystical way of Pythagorus, and the secret magic
of numbers.
Sir Thomas Browne (1605“1682) English writer and physician

This section is optional and requires some basic knowledge of the theory of
algebraic number ¬elds (see [164], for instance). The basic notion behind the
quadratic sieve and the MPQS studied in Section 5.4, is that we try to generate

many smooth quadratic residues of n close to n, where n is our composite
candidate for splitting. This notion was extended by Pollard5.15 in 1988 who
circulated a manuscript, in the factoring community, that was essentially the
template for a new√ integer factoring algorithm. The idea was to use cubic
integers (such as Z[ ’2]) to factor by trying to generate many smooth cubic
3

residues of √ close to 3 n. Later, the idea was extended to the ¬fth degree
n
(such as Z[ 5 2], for example) and used to factor the ninth Fermat number, F9
(see [138]). Pollard had been motivated in 1986 by the DLP given in [63],
where quadratic ¬elds were employed (for an overview of these developments
see [165, pp. 207“212]). Pollard then began to look at a more general scenario
by considering composite n ∈ N that are “close” to being powers, namely,

n = rt ’ s for small r, |s| ∈ N and larger t ∈ N. (5.12)

For instance, if |s| = 1, such numbers are called Cunningham numbers, which
have a rich history in factoring (see [46]), and factoring them has come to be
known as the Cunningham project, which began with the 1925 publication [65]
by Cunningham and Woodall.
The special number ¬eld sieve (SNFS), so called by the authors of [48], can
factor integers of type (5.12) in expected running time Ln (1/3, (32/9)1/3 ) (in the
notation of (B.5) on page 206), whereas the general number ¬eld sieve (GNFS),
which we will study below, has expected running time for arbitrary integers n
of Ln (1/3, 1.9229). This makes the SNFS asymptotically faster than any known
algorithm for the class of integers in (5.12), whereas the GNFS is a faster
algorithm for arbitrary integers.
The record for the GNFS is factorization of a 158-digit number (which
thereby completed the factorization of 2953 + 1, since the 158 digit number was
the last unsplit composite factor of it). This was accomplished as a product of a
73-digit prime and an 86-digit prime on January, 18, 2002 by F. Bahr, J. Franke,
5.15 John M. Pollard was born near London, England on October 25, 1941. He received
his B.A. in 1963, his M.A. in 1965, and his doctorate in 1978 all from Cambridge University,
England. He is a mathematician who worked for British Telecom from 1968 to 1986. Certainly,
he is best known for his research in cryptography, and has his name attached to several
algorithms, including: Pollard™s rho method, Pollard™s p ’ 1 method, and his introduction of
the number ¬eld sieve, as well as lattice sieving. On January 18, 1999, RSA Data Security
Inc. announced that he was a co-recipient of the 1999 RSA award. This award was instituted
in 1998 for recognition of those people and organizations that have made “signi¬cant, ongoing
contributions to security issues and cryptography in the areas of mathematics, public policy,
and industry.”



© 2003 by CRC Press LLC
5.5. Number Field Sieve 109

and T. Kleinjunj (with primality of the factors veri¬ed by Herman te Riele ” see
http://www.crypto-world.com/announcements/c158.txt). The previous record
was factorization of RSA-155, accomplished on August 22, 1999 by Herman te
Riele™s group (see http://www.crypto-world.com/announcements/RSA155.txt).
It is known that the record for the MPQS, cited on page 107, would have taken
about one-sixth the time used by the MPQS, if the GNFS had been used. In
fact, it took 8000 MIPS-years for the MPQS to factor the 135-digit number,
whereas it would have taken the GNFS about 1300 MIPS-years (see Footnote
3.7 on page 63). Similarly, it is known that the previous record of factoring
RSA-129 by the MPQS, would have taken a quarter of the time with the use of
the GNFS (see [77]). Hence, the following is now the clear front-runner as the
most accepted and widely used factoring algorithm.
In order to simplify the following description, we ¬rst set the stage. Despite
the fact that we are now going to be dealing with a much more powerful and
sophisticated algorithm for factoring, the basis underlying idea is still Fermat™s
di¬erence of squares method. Let™s give a simple preview.
The setup and the goal: Given a composite n to split, what we will
be setting out to achieve is the following. We select an appropriate monic
polynomial f (x), irreducible over Z, where m ∈ N with f (m) ≡ 0 (mod n), and
± ∈ C a root of f . This setup allows us to de¬ne the natural homomorphism,
φ : Z[±] ’ Z/nZ, via φ(±) = m which ensures that, for any g(x) ∈ Z[x], we
have φ(g(±)) ≡ g(m) (mod n). Thus, we will seek a set S of polynomials g over
Z such that both g∈S g(±) = β 2 ∈ Z[±], and g∈S g(m) = y 2 ∈ Z. Then by
setting φ(β) ≡ x (mod n) we get,
« 

x2 = φ(β)2 ≡ φ(β 2 ) ≡ φ  g(±) ≡ g(m) ≡ y 2 (mod n), (5.13)
g∈S g∈S

and we are back to Fermat™s method in (4.7) on page 89, where we have a
nontrivial factor of n if x ≡ ±y (mod n)! However, the devil is in the details so
here we go.
x General Number Field Sieve (GNFS)
We make some initial simplifying assumptions the reasons for which the
reader may ¬nd in [48]. We assume that a smoothness bound B and the degree
d of the polynomial f have been chosen from experimental data.5.16 Now, we
let m = n1/d and write n in base m,

n = md + cd’1 md’1 + · · · + c0 , with 0 ¤ cj ¤ m ’ 1 for j = 0, 1, . . . , d. (5.14)

Now set f (x) = xd + cd’1 xd’1 + · · · + c0 ∈ Z[x], and we have a monic
polynomial with f (m) = n. However, we wanted f to be irreducible. If it is
5.16 Heuristic complexity arguments determine the choices to be optimal when B = Ln (1/3, c)
for c = (8/9)1/3+ , and d = ((2/c)1/2 [ln n/(ln ln n)]1/3 ) = ln(Ln (1/3, (2/c)1/2 )). These
2
choices ensure that B d ≈ n2/d . Hence, n > 2d , which is needed to ensure that n is monic in
(5.14), a straightforward exercise to verify.



© 2003 by CRC Press LLC
110 5. Factoring

not, then we have no need of the number ¬eld sieve, since then f (x) = g(x)h(x)
where g and h have unequal positive degrees, so g(x)h(x) = f (m) = n, and we
have a nontrivial factor of n. Hence, we may assume that f is irreducible (as
are most monic polynomials over Z). Thus, we have our polynomial f , B, and
d values, and a number ¬eld F = Q(±) of degree d over Q.
In the following, we have to extend our de¬nition of smooth given in De¬ni-
tion 5.2. We call a + b± ∈ Z[±] B-smooth if |NF (a + b±)| is B-smooth where
NF is the norm map from the ¬eld F to Q. Also, for a given prime p ¤ B, set

R(p) = {r ∈ Z : 0 ¤ r ¤ p ’ 1 and f (r) ≡ 0 (mod p)}.

Then whenever (a, b) are coprime, p NF (a ’ b±) if and only if p (a ’ br) for
some r ∈ R(p) with p b. Then r is called the (unique) signature of N (a ’ b±)
modulo p. Hence, for each coprime (a, b)-pair, there exist |R(p)| = r primes
p ¤ B dividing N (a ’ b±). We will let these be denoted by p1 , p2 , . . . , pr . Then
if a ’ b± is B-smooth, we have:
r
N (a ’ b±) = (’1) pa(pi ) , where a(0) ∈ {0, 1}.
a(0)

i=1

Based on this we can now de¬ne exponent vectors. Let

v(a ’ b±) = (a(0), a(p1 ), a(p2 ), . . . , a(pr )).

However, based on our goal set above, we want not only a ’ b± to be B-
smooth, but also a ’ bm to be B-smooth. If the latter is the case, then let
qr+1 , qr+2 , . . . , qs be all the primes less than or equal to B dividing a ’ bm, and
write
s
b(qi )
a ’ bm = (’1) b(0)
qi ,
i=r+1

and de¬ne, v(a ’ bm) = (b(0), b(qr+1 ), . . . , b(qs )). Finally set

v(a, b) ≡ (v(a ’ b±), v(a ’ bm)) (mod 2).

Hence, v(a, b) is a binary vector of length r + s + 2.
For ease of elucidation, we make the simplifying assumption that if we ¬nd
a set S = {(a, b) ∈ Z — Z : gcd(a, b) = 1} such that (a,b)∈S v(a, b) is the
zero vector modulo 2, then both (a,b)∈S (a ’ bm) will be a square in Z and
(a,b)∈S (a ’ b±) will be a square in Z[±] (see [189] for the means of dealing with
the obstructions when this is not the case). Hence, all we do is to sieve over
coprime integer pairs (a, b) with 0 < b ¤ B, |a| ¤ B until the above is achieved.
Then we are in the situation (5.13) and we proceed to factor n.
There is also a variant of the SNFS developed by Dan Bernstein [25], called
the multiple-lattice number ¬eld sieve. He demonstrates that the formal relation
between the multiple-lattice number ¬eld sieve and the SNFS is the same as the
formal relation between the MPQS and the quadratic sieve.



© 2003 by CRC Press LLC