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