Prospects for Integer Factorisation Algorithms^{∗}

Richard P. Brent Computing Laboratory University of Oxford

rpb@comlab.ox.ac.uk

25 Sept 2001 Outline

∗Copyright \begin{matrix}c \\ ◯ \end{matrix}2001, R. P. Brent.  HK1t

• Introduction and motivation

• The elliptic curve method (ECM)

• The quadratic sieve (QS and MPQS)

• The number field sieve (NFS)

– Special (SNFS)

– General (GNFS)

• History and extrapolations

• Summary and conclusions

Introduction

Any positive integer N has a unique prime power decomposition

N = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{k}^{α_{k}}

(p_{1} < p_{2} < ⋯ < p_{k} primes, α_{j} > 0). The standard proof gives no hint of an efficient algorithm for computing the prime power decomposition. In order to compute it, we need –

1. An algorithm to test if an integer N is prime.

2. An algorithm to find a nontrivial factor f of a composite integer N.

Public Key Cryptography

Fortunately or unfortunately, depending on one’s point of view, problem 2 is generally believed to be hard. There is no known polynomial-time algorithm for finding a factor of a given composite integer N. This empirical fact is of great interest because the most popular algorithm for public-key cryptography, the RSA algorithm, would be insecure if a fast integer factorisation algorithm could be implemented.

Today I will survey some of the most successful integer factorisation algorithms, concentrating on the computational aspects, and particularly on parallel/distributed implementations. Due to shortage of time, many topics will be omitted. On my web site you can find a survey paper^{1} with many references to the literature.

1http://www.comlab.ox.ac.uk/oucl/work/ richard.brent/pub/pub196.html

Integer Factorisation Algorithms

There are many algorithms for finding a nontrivial factor f of a composite integer N. The most useful algorithms fall into one of two classes –

A. The run time depends mainly on the size of N, and is not strongly dependent on the size of f. Examples are –

– Lehman’s algorithm, which has worst-case run time O(N^{1/3}).

– The Multiple Polynomial Quadratic Sieve (MPQS) algorithm, which under plausible assumptions has expected run time

O(exp(\sqrt{c ln N ln ln N})) ,

where c ≈ 1 is a constant.

– The Number Field Sieve (NFS) algorithm, which under plausible assumptions has expected run time

O(exp(c(ln N)^{1/3}(ln ln N)^{2/3})) ,

where c is a (different) constant.

B. The run time depends mainly on the size of f, the factor found. (We can assume that f ≤ N^{1/2}.) Examples are –

– The trial division algorithm, which has run time O(f · (ln N)^{2}).

– Pollard’s “rho” algorithm, which under plausible assumptions has expected run time

O(f^{1/2} · (ln N)^{2}) .

– Lenstra’s Elliptic Curve (ECM) algorithm, which under plausible assumptions has expected run time

O(exp(\sqrt{c ln f ln ln f}) · (ln N)^{2}) ,

where c ≈ 2 is a constant.

In these examples, the time bounds are for a sequential machine, and the term (ln N)^{2} is a generous allowance for the cost of performing arithmetic operations on numbers which are O(N^{2}).

Quantum factorisation algorithms

In 1994 Shor showed that it is possible to factor in polynomial expected time on a quantum computer. However, despite the best efforts of several research groups, such a computer has not yet been built, and it remains unclear whether it will ever be feasible to build one. Thus, we restrict our attention to algorithms which run on classical (serial or parallel) computers.

Elliptic Curves Over Finite Fields

A curve of the form

y^{2} = x^{3} + ax + b  (1)

over some field F is known as an elliptic curve. A more general cubic in x and y can be reduced to the form (1), which is known as the Weierstrass normal form, by rational transformations, provided char(F) ≠ 2 or 3. There is a well-known way of defining an Abelian group (G, +) on an elliptic curve over a field. If P_{1} = (x_{1}, y_{1}) and P_{2} = (x_{2}, y_{2}) are points on the curve, then the point P_{3} = (x_{3}, y_{3}) = P_{1} + P_{2} is defined by –

(x_{3}, y_{3}) = (λ^{2} − x_{1} − x_{2}, λ(x_{1} − x_{3}) − y_{1}) ,

where

λ = \{ \begin{matrix}(3x_{1}^{2} + a)/(2y_{1}) & if P_{1} = P_{2} \\ (y_{1} − y_{2})/(x_{1} − x_{2}) & otherwise. \end{matrix}

The zero element in G is the “point at infinity”, (∞, ∞). We write it as 0.

Geometric Interpretation

The geometric interpretation of “+” is straightforward: the straight line P_{1}P_{2} intersects the elliptic curve at a third point P′_{3} = (x_{3}, −y_{3}), and P_{3} is the reflection of P′_{3} in the x-axis. More elegantly, if a straight line intersects the elliptic curve at three points Q_{1}, Q_{2}, Q_{3} then

Q_{1} + Q_{2} + Q_{3} = 0 .

Q_{1}  Q_{2}  Q_{3}

Figure 1: The Group Operation

Brief Description of ECM

The elliptic curve method (ECM) for integer factorisation was discovered by H. W. Lenstra, Jr. in 1985. Various practical refinements were suggested by Montgomery, Suyama, and others.

ECM uses groups defined by pseudo-random elliptic curves over GF(p), where p > 3 is the prime factor we hope to find. (Fortunately, we don’t need to know p in advance.) The group order g for an elliptic curve over GF(p) satisfies

|g − p − 1| < 2\sqrt{p} ,

and all g satisfying this inequality are possible. ECM is similar to an earlier method, Pollard’s “p − 1” method, but the p − 1 method has the disadvantage that the group is fixed and the method fails if p − 1 has a large prime factor. We can think of ECM as a “randomised” version of the p − 1 method. It works if we are lucky enough to hit a group whose order g has no large prime factors. (Jargon – g is “smooth”.)

Lenstra’s Analysis of ECM

Consider applying ECM to a composite integer N with smallest prime factor p. Making an unproved but plausible assumption regarding the distribution of prime factors of random integers in “short” intervals, Lenstra showed that ECM will find p in an expected number

W (p) = exp (\sqrt{(2 + o(1)) ln p ln ln p})

of multiplications (mod N), where the “o(1)” term tends to zero as p → ∞. In Lenstra’s algorithm the field F is the finite field GF(p) of p elements, where p is a prime factor of N. Since p is not known in advance, computation is performed in the ring Z/NZ of integers modulo N rather than in GF(p). We can regard this as using a redundant group representation.

One Trial of ECM

A trial (or curve) is the computation involving one random group G. The steps involved are –

1. Choose a parameter m.

2. Choose x_{0}, y_{0} and a randomly in [0, N). This defines b = y_{0}^{2} − (x_{0}^{3} + ax_{0}) mod N. Set P ← P_{0} = (x_{0}, y_{0}).

3. For each prime ≤ m take its maximal power q ≤ m and set P ← qP in the group G defined by a and b.

If P = 0 then the trial succeeds as a factor of N will have been found during an attempt to compute an inverse mod N. (We expect P = 0 if no prime power factors of the group order are larger than m.) Otherwise the trial fails. The work involved in a trial is O(m) group operations. There is a tradeoff involved in the choice of m, as a trial with large m is expensive, but a trial with small m is unlikely to succeed.

Optimal Choice of m

Making Lenstra’s plausible assumption, one may show that the optimal choice of m is m = p^{1/α}, where

α ∼ \sqrt{\frac{2 ln p}{ln ln p}} .

It follows that the expected run time is

T = p^{2/α+o(1/α)} .

The exponent 2/α should be compared with 1 (for trial division) or 1/2 (for Pollard’s “rho” method).

A Practical Problem

The optimal choice of m depends on the size of the factor p. Since p is unknown, we have to guess or use some sort of adaptive strategy. Fortunately, the expected performance of ECM is not very sensitive to the choice of parameters, so the precise strategy does not matter much.

Expected Performance of ECM

In Table 1 we give a small table of log_{10} W for factors of D decimal digits. The precise figures depend on assumptions about the implementation.

Table 1: Expected work for ECM

digits D log_{10} W
20  7.35
30  9.57
40  11.49
50  13.22
60  14.80

Note that in the region D = 50 to D = 60 the expected work W increases by a factor of about 2^{6}, and by Moore’s law we might predict that hardware will improve by this factor in about 9 years, i.e. Moore’s law gives about one digit per year.

ECM Example 1

After the factorisation of the ninth Fermat number F_{9} = 2^{2^{9}} + 1 in 1990 (we’ll say more about this later), F_{10} = 2^{2^{10}} + 1 was the “most wanted” number in various lists of composite numbers. F_{10} was proved composite in 1952 by Robinson, using Pépin’s test on the SWAC. A small factor, 45592577, was found by Selfridge in 1953 (also on the SWAC). Another small factor, 6487031809, was found by Brillhart in 1962 on an IBM 704. Brillhart later found that the cofactor was a 291-digit composite. Using ECM I found a 40-digit factor p_{40} =

4659775785220018543264560743076778192897

of F_{10} in October, 1995. The 252-digit cofactor c_{291}/p_{40} passed a probabilistic primality test and was soon proved to be prime using the method of Atkin and Morain (based, appropriately, on elliptic curves). Thus, the complete factorisation of F_{10} is

F_{10} = 45592577 · 6487031809 · p_{40} · p_{252} .

ECM Example 2

ECM can routinely find factors p of size up to 30 decimal digits, and it often finds larger factors. The largest factors known to have been found by ECM have 54 decimal digits (two of these were found by Lygeros and Mizony). I will give a slightly smaller example here because the number factored is perhaps more “interesting”. The 53-digit factor

p_{53} = 53625112691923843508117942\

311516428173021903300344567

of 2^{677} − 1 was found by Conrad Curry in September 1998 using a program written by George Woltman and running on 16 Pentiums. The group order for the lucky trial was

g = 2^{4} · 3^{9} · 3079 · 152077 · 172259 · 1067063 ·

3682177 · 3815423 · 8867563 · 15880351

We expect only one in 2, 400, 000 curves to have such a “smooth” group order.

ECM Factoring Records

1990 1992 1994 1996 1998 2000 2002 38 40 42 44 46 48 50 52 54 D

Figure 1: Factors found by ECM versus year

Figure 1 shows the size D (in decimal digits) of the largest factor found by ECM against the year it was done, from 1991 (40D) to the present (54D).

Curve Fitting

1990 1992 1994 1996 1998 2000 2002 6.0 6.2 6.4 6.6 6.8 7.0 7.2 7.4 7.6 ^{\sqrt{D}}

Figure 2: \sqrt{D} versus year Y for ECM

Let D be the number of decimal digits in the largest factor found by ECM up to a given date. From the theoretical time bound for ECM, assuming Moore’s law, we expect \sqrt{D} to be roughly a linear function of calendar year (in fact \sqrt{D ln D} should be linear, but given the other uncertainties we have assumed for simplicity that \sqrt{ln D} is roughly a constant).

Extrapolation of ECM Records

The straight line shown in the Figure 2 is

\sqrt{D} = \frac{Y − 1932.3}{9.3}

and extrapolation gives D = 60 in the year Y = 2004 and D = 70 in the year Y = 2010.

Quadratic Sieve Algorithms

Quadratic sieve algorithms belong to a large class of algorithms which try to find two integers x and y such that x ≠ ±y (mod N) but

x^{2} = y^{2} (mod N) .  (2)

Once such x and y are found, then GCD (x − y, N) is a nontrivial factor of N. One way to find x and y satisfying (2) is to find a set of relations of the form

u_{i}^{2} = v_{i}^{2}w_{i} (mod N),  (3)

where the w_{i} have all their prime factors in a moderately small set of primes (called the factor base). Each relation (3) gives a row in a matrix A whose columns correspond to the primes in the factor base.

Linear Algebra mod 2

Once enough rows have been generated, we can use sparse Gaussian elimination in GF(2) to find a linear dependency (mod 2) between a set of rows of A. Multiplying the corresponding relations now gives an expression of the form (2). With probability at least 1/2, we have x ≠ ±y mod N so a nontrivial factor of N will be found. If not, we need to obtain a different linear dependency and try again.

Exact and Approximate Systems

In the MPQS and NFS factorisation algorithms we have to solve very large, sparse linear systems exactly over the finite field GF(2). (More precisely, we have to find dependencies amongst the rows of a large matrix.) For discrete log problems we also get large sparse linear systems, although the field is different. More familiar to most people is the approximate solution of large sparse linear systems over the real or complex fields (using floating-point arithmetic).

Use of Iterative Methods

To avoid problems with “fill in”, variants of some familiar “iterative” methods can be used. These methods (based on conjugate gradients or Lanczos) only require matrix-vector multiplications and inner products. Some important points are:

• Nonzero vectors can be orthogonal to themselves !

• Many more iterations are required to find the exact solution (actually several exact dependencies) than an approximate solution.

• Preconditioning is useless (although other forms of preprocessing may be useful).

• The matrix is never symmetric.

• Operations over GF(2) can be parallelised using logical operations on words of (typically) 32 or 64 bits.

Sieving

In quadratic sieve algorithms the numbers w_{i} are the values of one (or more) polynomials with integer coefficients. This makes it easy to find relations by sieving. The inner loop of the sieving process has the form

while j < bound do

begin

s[j] ← s[j] + c; j ← j + q; end

Here bound depends on the size of the (single-precision real) sieve array s, q is a small prime or prime power, and c is a single-precision real constant depending on q (c = Λ(q) = ln p if q = p^{e}, p prime). It is possible to use scaling to avoid floating point additions, which is desirable on a small processor without floating-point hardware.

MPQS

MPQS is a quadratic sieve method which uses several polynomials to improve the efficiency of sieving (an idea of Montgomery). MPQS can, under plausible assumptions, factor a number N in time

Θ(exp \sqrt{c ln N ln ln N}) ,

where c ∼ 1.

If p ≈ \sqrt{N} this is essentially the same bound as for ECM. Thus, MPQS has no theoretical advantage over ECM. (Theoretically, ECM is almost always faster than MPQS).

However, in practice MPQS is usually faster than ECM if N is the product of two primes which both exceed N^{1/3}. This is because the inner loop of MPQS involves only single-precision (sieving) operations, whereas the corresponding loop of ECM involves multiple-precision operations mod N.

MPQS Examples

MPQS has been used to obtain many impressive factorisations. Arjen Lenstra and Mark Manasse (with many assistants scattered around the world) have factored several numbers larger than 10^{100}. For example, the 116-decimal digit number (3^{329} + 1)/(known small factors) was split into a product of 50-digit and 67-digit primes. The final factorisation is

3^{329} + 1 = 2^{2} · 547 · 16921 · 256057 · 36913801 ·
177140839 · 1534179947851 ·
2467707882284001426665277\
9036768062918372697435241 · p_{67}

Such factorisations require many years of CPU time, but a real time of only a month or so because of the number of different processors which are working in parallel.

The Magic Words are ⋯

At the time of writing, the largest number factored by MPQS is the 129-digit “RSA Challenge” number RSA129. It was factored in 1994 by Atkins et al. RS&A had predicted in Scientific American that it would take millions of years to factor RSA129. The factors of RSA129 allow decryption of a ‘secret’ message from RS&A. Using the decoding scheme 01 = A, 02 = B, …, 26 = Z, and 00 a space between words, the decoded message reads

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE

It is certainly feasible to factor larger numbers by MPQS, but for numbers of more than about 110 decimal digits GNFS is faster. For example, to factor RSA129 by MPQS required 5000 Mips-years, but to factor the slightly larger number RSA130 by GNFS required only 1000 Mips-years.

The Special Number Field Sieve (SNFS)

Most of our numerical examples have involved numbers of the form

a^{e} ± b ,  (4)

for small a and b, although the ECM and MPQS factorisation algorithms do not take advantage of this special form. The special number field sieve (SNFS) is a relatively new (c. 1990) algorithm which does take advantage of the special form (4). In concept it is similar to the quadratic sieve algorithm, but it works over an algebraic number field defined by a, e and b. The details are rather technical and depend on concepts from algebraic number theory, so we simply give two examples to show the power of the algorithm.

SNFS Example 1

Consider the 155-decimal digit number

F_{9} = N = 2^{2^{9}} + 1

as a candidate for factoring by SNFS. Note that 8N = m^{5} + 8, where m = 2^{103}. We may work in the number field Q(α), where α satisfies

α^{5} + 8 = 0,

and in the ring of integers of Q(α). Because

m^{5} + 8 = 0 (mod N),

the mapping ϕ : α ↦ m mod N is a ring homomorphism from Z[α] to Z/NZ. The idea is to search for pairs of small coprime integers u and v such that both the algebraic integer u + αv and the (rational) integer u + mv can be factored. The factor base now includes prime ideals and units as well as rational primes.

Example 1 continued

Because

ϕ(u + αv) = (u + mv) (mod N),

each such pair gives a relation analogous to (3). The prime ideal factorisation of u + αv can be obtained from the factorisation of the norm u^{5} − 8v^{5} of u + αv. Thus, we have to factor simultaneously two integers u + mv and |u^{5} − 8v^{5}|. Note that, for moderate u and v, both these integers are much smaller than N, in fact they are O(N^{1/d}), where d = 5 is the degree of the algebraic number field. Using these and related ideas, Lenstra et al factored F_{9} in June 1990, obtaining

F_{9} = 2424833 ·
745560282564788420833739\

5736200454918783366342657 · p_{99} ,

where p_{99} is an 99-digit prime, and the 7-digit factor was already known (although SNFS was unable to take advantage of this).

Details

The collection of relations took less than two months on a network of several hundred workstations. A sparse system of about 200,000 relations was reduced to a dense matrix with about 72,000 rows. Using Gaussian elimination, dependencies (mod 2) between the rows were found in three hours on a Connection Machine. These dependencies implied equations of the form x^{2} = y^{2} mod F_{9}. The second such equation was nontrivial and gave the desired factorisation of F_{9}.

SNFS Example 2

The current SNFS record is the 233-digit number 2^{773} + 1, factored in November 2000 by a collaboration called “The Cabal”.

In fact, 2^{773} + 1 = 3 · 533371 · p_{55} · p_{71} · p_{102}, where the 6-digit factor was already known, leaving a 227-digit composite number. The large factors are:

p_{55} = 17376397426392540604378615\

21344464381695829802369522859 ,

p_{71} = 23206316220078396404383\
777135534261928387046186\
611079662143434527093563 ,

and p_{102} may be found by division (exercise).

It is curious that p_{55} might have been found by ECM, but this would not have helped as the 172-digit quotient would have been just as hard to factor as the original number!

For details see the announcement at

ftp://ftp.cwi.nl/pub/herman/NFSrecords/
SNFS-233 .

A Few Details

The factorisation of N = 2^{773} + 1 used two polynomials

f(x) = x − 2^{129}

and

g(x) = x^{6} + 2

with common root m = 2^{129} mod N.

After sieving and reduction a sparse matrix over GF(2) was obtained with about 6.75 × 10^{6} rows and weight (number of nonzero entries) about 4.4 × 10^{8}, an average of about 65 nonzeros per row. Montgomery’s block Lanczos program took 250 CPU hours on a Cray C90 to find 64 dependencies.

Finally, the square root program needed 19 hours on one CPU of an SGI Origin 2000, and three dependencies to find the three large prime factors.

The General Number Field Sieve (GNFS)

The general number field sieve (GNFS or just NFS) is a logical extension of the special number field sieve (SNFS). When using SNFS to factor an integer N, we require two polynomials f(x) and g(x) with a common root m mod N but no common root over the field of complex numbers. If N has the special form a^{e} ± b then it is usually easy to write down suitable polynomials with small coefficients, as illustrated by the two examples given above. If N has no special form, but is just some given composite number, we can also find f(x) and g(x), but they no longer have small coefficients.

The “Base m” Method

Suppose that g(x) has degree d > 1 and f(x) is linear. d is chosen empirically, but it is known from theoretical considerations that the optimum value is

d ∼ (\frac{3 ln N}{ln ln N} )^{1/3} .

We choose m = ⌊N^{1/(d+1)}⌋ and write

N = ∑_{j=0}^{d} a_{j}m^{j}

where the a_{j} are “base m digits”. Then, defining

f(x) = x − m, g(x) = ∑_{j=0}^{d} a_{j}x^{j} ,

it is clear that f(x) and g(x) have a common root m mod N. This method of polynomial selection is called the “base m” method.

Other Ingredients of GNFS

Having found two appropriate polynomials, we can proceed as in SNFS, but many difficulties arise because of the large coefficients of g(x). The details are the subject of several theses. Suffice it to say that the difficulties can be overcome and the method works! Due to the constant factors involved, GNFS is slower than MPQS for numbers of less than about 110 decimal digits, but faster than MPQS for sufficiently large numbers, as anticipated from the theoretical run times.

Difficulties Overcome

Some of the difficulties which had to be overcome to turn GNFS into a practical algorithm are:

• Polynomial selection. The “base m” method is not very good. Peter Montgomery and Brian Murphy have shown how a very considerable improvement (by a factor of more than ten) can be obtained.

• Linear algebra. After sieving a very large, sparse linear system over GF(2) is obtained, and we want to find dependencies amongst the rows. It is not practical to do this by Gaussian elimination because the “fill in” is too large. Montgomery showed that the Lanczos method could be adapted for this purpose. (This is nontrivial because a nonzero vector x over GF(2) can be orthogonal to itself, i.e. x^{T} x = 0.) His program works with blocks of size 64.

Difficulties continued

• Square roots. The final stage of GNFS involves finding the square root of a (very large) product of algebraic numbers. Once again, Montgomery found a way to do this.

• An idea of Adleman, using quadratic characters, is essential to ensure that the desired square root exists with high probability.

Scalability of GNFS

At present, the main obstacle to a fully parallel and scalable implementation of GNFS is the linear algebra. Montgomery’s block Lanczos program runs on a single processor and requires enough memory to store the sparse matrix. It is possible to distribute the block Lanczos solution over several processors of a parallel machine, but the communication to computation ratio is high. There are some interesting tradeoffs here –

• By increasing the time spent on sieving we can reduce the size and weight of the resulting matrix.

• By performing some steps of Gaussian elimination, we can reduce the communication requirement for the iterative solution, at the expense of increasing the storage requirements.

RSA155

At the present time (March 2001), the largest number factored by GNFS is the 155-digit RSA Challenge number RSA155. It was split into the product of two 78-digit primes on 22 August 1999 (only six months after the 140-digit number RSA140), by a team coordinated from CWI, Amsterdam.

Some Statistics

The total amount of CPU time spent on sieving was 8000 Mips-years on assorted machines (calendar time 3.7 months). The resulting matrix had about 6.7 × 10^{6} rows and weight (number of nonzeros) about 4.2 × 10^{8} (about 62 nonzeros per row). Using Montgomery’s block Lanczos program, it took almost 224 CPU-hours and 2 GB of memory on a Cray C916 to find 64 dependencies. Calendar time for this was 9.5 days.

Polynomial Selection for RSA155

The two polynomials used to factor RSA155 were

f(x) = x − 39123079721168000771313449081

and

g(x) = +119377138320x^{5}

−80168937284997582x^{4} −66269852234118574445x^{3} +11816848430079521880356852x^{2} +7459661580071786443919743056x −40679843542362159361913708405064 .

Polynomial Selection cont.

Using ideas due to Peter Montgomery and Brian Murphy, the polynomial g(x) was chosen to have a good combination of two properties: being unusually small over the sieving region and having unusually many roots modulo small primes (and prime powers).

The second property alone makes g(x) as effective at generating relations as a polynomial chosen at random for an integer of 137 decimal digits (so in effect we have removed at least 18 digits from RSA155 by judicious polynomial selection).

The polynomial selection took approximately 100 Mips-years or about 1.25% of the total factorisation time.

Summary – RSA140 and RSA155

In Table 2 we summarise the RSA140 and RSA155 factorisations. Extrapolation is tempting, but dangerous because there were algorithmic improvements which helped the RSA155 factorisation, and there was a psychological incentive to factor a 512-bit number.

Table 2: RSA140 and RSA155 factorisations

RSA140 RSA155
Date completed  Feb. 1999 Aug. 1999
Total mips-years 2000 8000

Improvement due to

polynomial selection 8 14
Matrix rows  4.7 × 10^{6} 6.7 × 10^{6}
Total nonzeros  1.5 × 10^{8} 4.2 × 10^{8}
Nonzeros per row 32 62

Matrix solution time

(on Cray C916)  100 hours 224 hours

The “Cipher Challenge”

There has been much interest in Simon Singh’s recent book The Code Book and the associated “Cipher Challenge”. This Challenge is a collection of ten encrypted messages, with a prize of £10000 offered for the first complete solution. It was solved on 7 October 2000 by a Swedish team (Almgren, Andersson, Granlund, Ivansson and Ulfberg). For details see

http://www.simonsingh.com/cipher.htm
and http://codebook.org/

The tenth and most difficult problem involved RSA encryption with a 512-bit key (very slightly smaller than RSA155). The Swedish team factored this by GNFS, using the programs developed at CWI for RSA155, and about twice as much computer time. The sieving was done on several hundred workstations at NADA. The linear algebra involved 8.4 × 10^{6} equations with 5 × 10^{8} nonzeros, and was done on a quad-processor Compaq ES40 in 13 days.

A Backdoor

The RSA modulus N = p_{77} · p_{78} is a product of 77 and 78-digit primes, and p_{78} − 1 has the factorisation

2 · 224774533 · 451911151 · 1031140207· 1336679039 · 2303217611 · 6890518249 · 15318284953 · 12286770953753

This factorisation is extremely “non-random”. There are no small factors (except for the necessary factor 2); neither are there are any very large factors. The two largest factors are “just right” for a good implementation of the Pollard p − 1 method to succeed in a reasonable time. The middle factors have 28, 29, 30, 31, 32, 33 and 34 bits. Paul Leyland has confirmed that a “backdoor” was created intentionally.

It would have been possible to factor the RSA modulus in about two days on a 500 Mhz alpha using the Pollard p − 1 method, instead of the 67 CPU-years required by GNFS !

Unfortunately, the Swedish team did not try the Pollard p − 1 method, and those competitors who did must have given up too soon.

Historical Factoring Records

1960 1970 1980 1990 2000 0 20 40 60 80 100 120 140 160

Size of “general” number factored versus year

The graph shows the size (in decimal digits) of the largest “general” number factored against the year it was done, from 1964 (20D) to the present (155D) (historical data from

www.rsa.com).

Curve Fitting and Extrapolation

1960 1970 1980 1990 2000 Y 0 1 2 3 4 5 6 7 8 D^{1/3}

From the theoretical time bound for GNFS, assuming Moore’s law, we expect D^{1/3} to be roughly a linear function of time (we have assumed that (ln D)^{2/3} is roughly a constant). The graph shows D^{1/3} versus year Y. The straight line is

D^{1/3} = \frac{Y − 1928.6}{13.24}

and extrapolation, for what it is worth, gives D = 309 (i.e. 1024 bits) in the year Y = 2018.

Predictions

Moore’s law predicts that circuit densities will double every 18 months or so.

• As long as Moore’s law continues to apply and results in correspondingly more powerful parallel computers, we expect to get 3–4 decimal digits per year improvement in the capabilities of GNFS, without any algorithmic improvements.

• The extrapolation from historical figures is more optimistic: it predicts 6–7 decimal digits per year in the near future.

• Similar arguments apply to ECM, for which we expect between 1.0 and 1.5 decimal digits per year in the size of factor found.

Implications for RSA

512-bit RSA keys are clearly insecure. 1024-bit RSA keys should remain secure for at least fifteen years, barring the unexpected (but unpredictable) discovery of a completely new algorithm which is better than GNFS, or the development of a practical quantum computer.

Over the past twenty years, factorisation algorithms have improved to the point where it is time to seriously consider replacing the RSA cryptosystem with another system which depends on a “harder” problem, e.g. the El Gamal algorithm using the discrete logarithm problem for elliptic curves over large finite fields.

Summary and Conclusions

I have sketched some algorithms for integer factorisation. The most important are ECM, MPQS and GNFS. The algorithms draw on results in elementary number theory, algebraic number theory and probability theory. As well as their inherent interest and applicability to other areas of mathematics, advances in public key cryptography have lent them practical importance. Until a polynomial time algorithm is found or a quantum computer capable of running Shor’s algorithm is built, large factorisations will remain an interesting challenge.