Evaluation Report on the Factoring Problem
Jacques Stern

1

Introduction

This document is an evaluation of the factoring problem, as a basis for designing
cryptographic schemes. It relies on the analysis of numerous research papers on thesubject.
The present report is organized as follows: firstly, we review the factoring problem
and several related problems such as the problem of extracting e-th roots, which forms
the basis of the RSA cryptosystem. Next, we analyze the various algorithms that are
currently known to solve the problem. For each algorithm, we study its asymptotic
behaviour, as well as its practical running time, based on experiments reported in theliterature. Finally, we derive consequences in terms of key sizes for cryptosystems
whose security depend on the hardness of factoring. We conclude by making somepredictions on how the key sizes might evolve. This is as requested by IPA.

2

Factoring and related problems

In this section, we review the problem of factoring integers and several related problems,
and we investigate their security in terms of complexity-theoretic reductions. Besides
the problem of extracting e-th roots, which forms the basis of the RSA cryptosystem,
we cover the strong RSA problem and the approximate e-th root problem AERP, whichhave been recently considered in relation with various cryptographic schemes.

2.1

Factoring as a cryptographic primitive

It is well known that any integer n can be obtained, in a unique manner, as the productof non necessarily distinct prime numbers. Factoring n consists in finding the list ofsuch primes, also called the prime decomposition of n. Of particular interest, is thecase of integers n, which are the product of two prime factors p and q.
The basic security assumption on which numerous cryptosystems rely is the hardness of factoring: an attacker cannot find the prime decomposition of n. In a more precise complexity-theoretic framework, this means that the success probability Succfact (A)1of any polynomial time algorithm A attempting to factor n is negligible, i.e. asymptotically smaller than the inverse of any polynomial function of the security parameter.
Probabilities are taken over n and the random coins of A. The security parameter k is
directly related to the bit-size of n. For example, one can simply set k = |n|. In mostcryptographic applications, especially in the case of integers of the form n = pq, n is
not chosen at random, but is, implicitly or explicitly, produced by a key generation
algorithm K(1k ). In the case of the RSA cryptosystem, the key generation algorithm,
chooses, on input k, two large primes p, q of equal size and issues the so-called modulus
n = pq. The sizes of p, q are set in such a way that the binary length |n| of n equals
2k. Further tests, related to the factors of p − 1 and q − 1 are usually included thatavoid weak moduli. This restricts the family of integers that A attempts to factor tothose output by the key generation algorithm K(1k ). In this case probabilities also
range over the random coins that K uses.
To go from asymptotic to exact estimates, we can define Succfact (τ, k) as the probability for an adversary to factor a given integer within time τ . We turn the above into
symbols, in the case of integers n of the form p, q, p < q:Succfact (A) = Pr[n ← K(1k ), n = pq : A(n) = p].
The hardness of the factoring is the statement that, for large enough k, this probability
is extremely small.
Many cryptographic schemes rely on the assumption that factoring is hard, and, at
this point, we will simply mention the celebrated RSA algorithm proposed by Rivest,
Shamir and Adleman [51].

2.2

RSA and related schemes

The modern approach to cryptographic design relies on the notion of security proof.
Such proofs are reductions in the sense of complexity theory. Given an attacker A
that breaks the cryptographic scheme, one designs another machine B, solving theunderlying hard problem. The relation between running times and success probabilities
of A and B is further made explicit, so that, if the security loss is not too large, concrete
estimates on key sizes may be derived from the proof.
Ideally, one would like to establish the security of a scheme based on the soleassumption that the underlying problem is hard. Unfortunately, very few schemes
allow such a proof. For the others, the best one can hope for is a proof carried in a
non-standard computational model, as proposed by Bellare and Rogaway [4], following
an earlier suggestion by Fiat and Shamir [27]. In this model, called the random oracle
model, concrete objects such that hash functions are treated as random objects. This
allows to carry through the usual reduction arguments to the context of relativized
computations, where the hash function is treated as an oracle returning a random2

answer for each new query. A reduction still uses an adversary as a subroutine of aprogram that contradicts a mathematical assumption, such as the hardness of factoring
However, probabilities are taken not only over coin tosses but also over the random
oracle.
In the case of factoring, whatever the computational model is, it is often the casethat security is not related to the problem itself, but rather to the question of extracting
e-th root modulo n. The case e = 2 is the problem of extracting modular squareroots, which is easily shown equivalent to factoring. The general case is related to
the RSA cryptosystem. At key generation, an exponent e, relatively prime to ϕ(n) =(p − 1)(q − 1) is chosen, and the corresponding RSA function is defined by
x :−→ (xe ) mod n
The main conjecture related to this function is its one-wayness (OW): using only publicdata, an attacker cannot invert the function. More precisely, denote by Succrsa (τ, k)
the probability for an adversary to find the preimage of a given element within time τ ,in symbols:
Succrsa (τ, k) = Pr[(n, e) ← K(1k ), y ← ZN , x ← A(n, e, y) : y = xe mod n],then, for large enough moduli, this probability is extremely small. The asymptotic
version states that, when A has running time bounded by a polynomial function τ ofthe security parameter, Succrsa (τ, k) eventually becomes smaller than the inverse of any
polynomial in k.
It is well known that, if d is the inverse of e modulo ϕ(n), y d mod n computes theinverse of the RSA function. Thus, the factorization of n allows to invert the RSA
function, since d can be computed from p and q. It is unknown whether the converse istrue, i.e. whether factoring and inverting RSA are computationally equivalent. There
are indications that it might not be true (see [8]). Thus, the assumption that RSA is
one-way might be a stronger assumption than the hardness of factoring. Still, it is a
widely believed assumption, and the only method to assess the strength of RSA is tocheck whether the size of the modulus n outreaches the current performances of thevarious factoring algorithms.
The strong RSA problem, attempts to find x and e > 1, such that xe = y mod n,given an element y in Z?n . The assumption that the problem is hard is stronger than the
RSA assumption, that was just considered above. This hypothesis has been recently
used as a basis for the security of several cryptographic schemes. Of particular interestis the Cramer-Shoup signature scheme [11], where the security proof is carried in thestandard model of computation, without any random oracle.
Another problem that has been considered in [45] is the approximate e-th root
problem (AERP: given n and y in Z?n , find x such that xe mod n lies in a prescribedinterval centered at y. Of particular interest is the case when the length of the interval3

is of the order of n2/3 , which forms the basis of the ESIGN [25, 45] signature scheme.
In this case, the key generation algorithms produces moduli of but-size 3k, where kis the security parameter and the exact format of the problem is to find x such thaty ≤ xe mod n < y + 22k−1 . Again, computing the inverse of the RSA function clearly
allows to solve the AERP problem. It is unknown whether the converse is true, i.e.
whether AERP and inverting RSA are computationally equivalent. This is conjecturedin [26], as soon as e ≥ 4.
It should be mentioned that the ESIGN signature scheme uses moduli of the form
2
p q, where p and q are primes of size k = |n|. This is related to an algebraic property
3of exponentiation modulo such integers, which offers an extremely efficient way to findan element of Z?n whose e-th power lies in a prescribed interval of length at least pq.
Moduli with three or more distinct factors are also being considered in the setting ofmultiprime RSA (see [54]).
In conclusion, the only method known to attack the RSA problem, as well as its
variants, including AERP, is is to factor the modulus. Therefore, in order to estimate
whether the parameters of a cryptographic scheme, relying on the hardness of these
problems, offer a wide security margin, one needs to refer to the performances of thevarious algorithms known for factoring.

3

Algorithms for factoring

As was just observed, the security of many cryptographic schemes can only be measured
in terms of the hardness of factoring integers. We now review the known factoringalgorithms. Before discussing the two main general purpose factoring algorithms, thequadratic sive (QS) and the number field sive (NFS), we decribe two specific families ofalgorithms, respectively covering the case where the number n to factor has relatively
small factor, and the case where there are repeated factors.

3.1

Factoring techniques sensitive to the size of the smaller
factor3.1.1

Pollard’s ρ-method.

Assume that the modulus to factor is denoted by n and its smallest factor by p. The
idea behind the method is to iterate a polynomial P with integer coefficients, that is tosay computing x1 = P (x0 ) mod n, x2 = P (P (x0 )) mod n, etc. We try to find a collision
modulo p, i.e. two values x and x0 such that x = x0 mod p. Since it is extremely unlikelythat the same equality holds modulo n, we then factor n by computing the g.c.d. ofx − x0 and n. P is usually taken to be x2 − 1.
Collison search is an extremely well understood problem whose time complexity is4√O( p) and which can be programmed efficiently. The problem here is that the collison
test is a gcd computation, which slows down the whole algorithm. Although there areseveral optimizations, the ρ-method can only be used to cast out small factors of an
integer (say 30-digit factors). As far as we know, it has not been used to find significantly larger factors. Although large scale collision search seems possible, following theideas in [57], experiments along these lines have not been reported in the literature.
3.1.2

The p − 1 method.

Let B be a positive integer. A number is B-smooth if it is of a product of prime
numbers all < B. B-smooth numbers are usually used through a table of primes < B.
The p − 1 method relies on the use of Fermat’s little theorem: if p − 1 happens to be
B-smooth, then the gcd of n and a`(B) − 1 factors n, where `(B) is the product of allprime factors < B.
Of course, the p−1 method only works if p−1 is smooth. Therefore, it is quite irrelevant to cryptography, since key generation algorithms usually eliminate such primes.
We have included the method in the present report as a step towards more efficienttechniques.
3.1.3

The elliptic curve method.

The ECM is a generalization of the p − 1 method, for which the above simple countermeasure is not sufficient. Consider an elliptic curve modn with equationy 2 = x3 + ax + 1
If the number of points of this curve modulo p is B-smooth, then a factor of n can be
discovered along the computation of the scalar multiplication of M0 = (0, 1) by `(B),
according to the group law of the elliptic curve.
As for many factoring algorithms the success probability of the algorithm, and theresulting complexity estimates, are naturally expressed in terms of the L-function:
Lq [s; c] = exp(c(ln q)s (ln ln q)1−s ).
The reason why this function is involved is its relation with the asymptotic probability
that a random element can be factored into elements of a factor base (see [29, 46]).
For instance, it is known that the probability that a random integer < Lx [ν; λ] has all
its prime factors < Lx [w; µ] is asymptotically
Lx [ν − w; −λ(ν − w)/µ + o(1)].
Using such estimates, it can be shown that the elliptic curve is L√
p [1/2; α]-smoothwith probability Lp [1/2; −1/(2α) √+ o(1)]. This is minimal for α = 1/ 2 and gives an
expected running time of Lp [1/2; 2 + o(1)] group operations on the curve.
5There have been several improvements of ECM factoring, notably the FFT extension of P. Montgomery. Furthermore, several implementations of ECM are available.
The current ECM factoring record was established in december 1999, when a prime
factor with 54 digits of a 127-digit composite number n was found with GMP-ECM,
a free implementation of the Elliptic Curve Method (see [39]). The limit used was
B = 15, 000, 000.
In a recent paper [9], Richard Brent extrapolates the ECM record to be of D digits
at year about√
Y = 9.3 ∗ D + 1932.3
this would give records of D = 60 digits at year Y = 2004 and D = 70 at year 2010.
Such record would need B ' 2, 900, 000, 000 and require testing something like 340, 000
curves. It can be noted that, if Brent’s prediction is correct, moduli with factors of 256
bits will become insecure at year Y = 2014. It should be noted that the ECM method
decribed in this section is superseded by the algorithms that appear further on in thepresent report. However, since its computing time is related to the size of the smallest
factor p of n, ECM gives an indication on the minimum size of p. Accordingly, it limits
the number of distinct prime factors of equal size that can be allowed for multiprime
schemes, when the size of the modulus is given.

3.2

Specific factoring techniques for numbers of the form pr q

In recent work (see [7]), a new factoring method that applies to integers of the form
pr q has been found. The method is based on an earlier result of Coppersmith (see[18]),
showing that an RSA modulus n = pq, with p, q of the same size, can be factored
given half the most significant bits of p. It turns out that, for numbers of the formn = pr q, with p, q of the same size, fewer bits are needed. In the sequel we let c be areal constant such that q ' pc . In many cases of interest for cryptography, c is set to1.
Note that disclosing the leading bits of p provides a rough approximation P of
p. What remains to be found is the difference x0 = p − P . Note that x0 is a rootof f (x) = (x + P )r , modulo pr . The new method is based on finding polynomials
with short enough integer coefficients, which vanish at x0 modulo some power prm of
p. It relies on techniques that find small solutions to modular polynomial equations,investigated by Coppersmith [17, 19], Howgrave-Graham [30] and Jutla [32]. The key
result is the following simple lemma:
Lemma 3.1 Let h(x) be a polynomial of degree√ d with integer coefficients and let X
be a positive integer. Assume ||h(xX)|| < M/ d. If h(x0 ) = 0 (mod M ) and |x0 | < X,
then h(x0 ) = 0 holds over the integers.

6√
Proof. From the Cauchy inequality, we get that |h(x0 )| is bounded by √Md d = M .
Hence the result.
The lemma suggests to look for polynomials h(x), such that h(x) has x0 as a root
modulo M = prm , where m is an appropriate integer, and h(xX) has norm less thanroughly prm . We let
gi,k (x) = nm−k xi f (x)j .
Observe that x0 is a root of gi,k (x) modulo M , for all i and all k = 0, . . . , m. Thus,in order to apply the lemma, it is enough to find a polynomial of small enough normin the lattice L generated by various gi,k (xX) of bounded degree. This is a standard
lattice reduction problem.
We use d such polynomials, where d > mr, will be determined later.
1. all gi,k (x), with i = 0, . . . , r − 1 and k = 0, . . . , m − 1,
2. all gj,m (x), with j = 0, . . . , d − mr − 1.
The determinant of the lattice L is easily seen to be the product of the leading coefficients
2∆ = X d /2 nrm(m+1)/2
Based on LLL heuristics [31], short vectors of this lattice should therefore be aroundrm(m+1)
X d/2 n 2d . When using the LLL algorithm, there is a further multiplicative factor
2d/2 (see [34]), but we do not take this into account. Thus the method is heuristicallyvalid when√rm(m+1)
X d/2 n 2d < prm / d√
Again, we forget the d term, as we did for the 2d/2 multiplicative factor and obtain:
X d/2 < p−rm(m+1)(r+c)
2d

prm

d
d
The optimal value of m is attained at b r+c− 21 c and we may choose d so that r+c
is1
within 2(r+c) of an integer. Working through arithmetics yields the boundrc

X < p1− r+1 − d (1+δ)
with

1
r+c
−
r+c
4d
Since δ is < 1, we obtain the simpler bound
δ=

c

r

X < p1− r+1 −2 d

7

To conclude, lattice reduction will find a polynomial that vanishes at x0 over the
integers if the bound X for the difference p − P is bounded bycr

p1− r+1 −2 dAt this point, any standard root-finding algorithm will disclose x0 , and therefore p.
Note that, when p, q are of almost equal size, c = 1, we can take d of the order of2r and ignore the term 2 dr . This means that factoring is performed by lattice reduction
as soon as an approximation P of p is known, such that1

|P − p| < p1− r+1
1
In other words, it is enough to guess a fraction r+1of the leading bits of p, to be able
to factor n.
Comparing the above estimate with the running time for√ECM, one can see that the
new method beats ECM for r larger than, approximately ln p. Several experiments
are reported in [7]. For example, the authors were able to factor a 768 bit modulus,
with p, q of equal bit-size 96 and r = 7, given the 22 leading bits of p. The running
time for LLL was 10 hours. No experiments appears possible when r = 1, 2 or 3,
which are the cases of interest for cryptography. Thus, for very small values of r, thealgorithm is certainly impractical.
We close this section by mentioning that it is also possible to slightly speed up ECM
for numbers of the form p2 q (see [47], even though this does not apply to n = pd q, with
odd d. Despite, its academic value, the improvement does not change the order ofmagnitude of the running time for ECM.

3.3

The Quadratic Sieve.

The quadratic sieve method (QS) factors n by gathering many congruences of the form
x2 = (−1)e0 pe11 · · · pemm
where p1 , · · · , pm is a list of prime numbers < B,√
called the factor base. This is done byfinding B-smooth numbers of the form Q(a) = ( n + a)2 − n. It turns out that there isa very efficient sieving process that performs the job without division, hence the name
QS. Once enough congruences have been gathered, one obtains another congruence ofthe same type with all exponents ei even: this is done by Gaussian elimination mod2.
Thus one gets a relation x2 = y 2 mod n and, with significant probability, computing
gcd(x−y, n) factors n. The time complexity of QS is L[1/2; 1+o(1)] but, as it uses very
simple operations, it is usually more efficient than ECM for numbers whose smallest
prime factor exceeds n1/3 .

8

Many improvements of the basic method have been found, notably the multiple
polynomial variation (MPQS) and the large prime variation. This has led to very efficient implementation and, until the mid-nineties, was used to set up factoring records.
The largest number factored by MPQS is the 129-digit number from the “RSA Challenge” (see [53]). It was factored in april 1994 and took approximately 5000 mips-years(see [3]).

3.4

The Number Field Sieve.

The number field sieve (NFS) is somehow similar to the QS but it searches for congruences in some number field (algebraic extension of the rational numbers). The method
was first introduced in 1988 by John Pollard [49] to factor numbers of the form x3 + k.
It was quickly extended to handle numbers of the form re +s for small positive r and |s|:this was successfully applied to the Fermat number F9 = 2512 +1 (see [37]). This versionof the algorithm is now called the special number field sieve (SNFS) [36], in contrast
with the general number field sieve (GNFS) [10], which can handle arbitrary integers.
GNFS factors integers n in heuristic time Ln [1/3; c + o(1)], with c = (64/9)1/3 ≈ 1.9.
This is asymptotically considerably better than QS.
3.4.1

Overview

The number field sieve (NFS) first selects two low-degree irreducible polynomials f1 (X)and f2 (X) in Z[X] with small coefficients, such that f1 (X) and f2 (X) have a common
root m modulo n. These polynomials define two number fields Q(α1 ) and Q(α2 ).
Because m is a root, there is a natural ring homomorphism ϕj from Z[αj ] to Zn(j ∈ {1, 2}), induced by ϕj (αj ) = m. We extend ϕj to the field Q(αj ), ignoring
potential divisibility problems, which only appear if n gets factored.
The ring of integers of a number field is not necessarily a unique factorization
domain, but the ring of fractional ideals always is. Thus, the NFS selects two ideal
factor bases B1 and B2 (corresponding to Q(α1 ) and Q(α2 )) consisting of prime ideals
of norm only divisible by small primes. We define smoothness as follows: a fractional
ideal I of Q(αj ) is smooth if it can be factored completely over the factor base Bj , andan algebraic number x is smooth if the fractional ideal hxi it spans is smooth.
By sieving, the NFS finds a huge collection of pairs (ai , bi ) of small integers suchthat each ai − bi αj is smooth: as a result, the factorization of hai − bi αj i is known.
Linear algebra modulo
Q 2 produces many sets S of indices such that, for each j = 1, 2,
the fractional ideal i∈S
Q hai − bi αj i is a square. This does not necessarily mean thatthe algebraic number i∈S (ai − bi αj ) is a square in Q(αj ). However, using specificcharacters defined
Q from Q(αj ) to Z2 , Adleman [1] was able to add a few linear equations
to ensure that i (ai − bi αj ) is in fact a square in Q(αj ). If both algebraic numbers are9squares, the following congruence
ϕ1!
Y(ai − bi α1 ) ≡ ϕ2!
Y(ai − bi α2 ) (mod n),

i∈S

i∈S

can be rewritten as a congruence of squares:

2

2
sY
sY
ϕ1 
(ai − bi α1 ) ≡ ϕ2 (ai − bi α2 ) (mod n).
i∈S

i∈S

If it is possible to extract square roots of gigantic algebraic numbers, this yields a nontrivial factor of n with significant probability. We now comment on the various stepsof the algorithm.
3.4.2

Polynomial selection

This is where the GNFS differs from the SNFS: in the SNFS, the polynomials arederived from the special form of the number n to factor. Few polynomial selection
methods for the GNFS have been proposed. Most of them are based on the principle
described in [10]: first select m around n1/(d+1) , where d is a small integer chosen
according to the size of n, and expand n in base m. This produces a first polynomial
f1 of degree d, while the second polynomial is set to f2 (x) = x − m. Several suchpairs are chosen and a bit of sieving is performed to see which pair gives the best
results. Recently, Montgomery and Murphy (see [43, 13, 14]) refined this construction:
they suggested additional tests for selecting the polynomials based on the number ofroots modulo small primes. Polynomial which have many roots modulo small primes,
behave much better. Trial and error is still used, once several pairs have been selected.
In [14], the authors estimated that the new polynomial selection was four times better
than what was expected from the former method. In [22, 23], Montgomery proposed
another construction outputting a pair of quadratic polynomials rather than a highdegree polynomial and a linear one. However this construction does not appear optimal.
3.4.3

Sieving

In this stage, one tries to find many pairs of small integers ai and bi such that eachai − bi αj is smooth. There are basically two techniques: lattice sieving and line sieving.
Assume that the second polynomial f2 is linear, as is the case in practice. In latticesieving [50], one fixes a prime q and finds pairs (ai , bi ) such that (ai −bi α1 )/q and ai −bi α2are smooth. This is repeated for many special q’s. In line sieving (see [22, 23]), one
fixes a value of bi , and finds values of ai in a given interval, for which both ai − bi α1and ai − bi α2 are smooth. Recents experiments [13, 14] used both lattice sieving and10

line sieving, although this is somehow redundant. This follows from the fact that thecode for lattice sieving does not currently allow large factor bases.
3.4.4

Linear algebra

The linear algebra has a first technical step, which we do not describe in detail, since
it depends on many details of the sieving procedure, which we omitted. It consists indeleting equartions and minimizing their number, as well as the number of unknowns.
The filtering procedure used in recent experiments [13, 14] is due to Cavallar [12].
The time-consuming part of the linear algebra is devoted to solving a huge sparselinear system modulo 2. Applying structured Gaussian elimination is not recommended
when the system is huge, due to memory constraints. Instead, one prefers to use either
the Lanczos (see [33]) or Wiedemann [58] algorithms, or one of their variants. These
are iterative algorithms: instead of modifying the input matrix, they repeatedly apply
the input matrix to a vector. Thus, they only store, besides the original matrix, a few
temporary vectors. The Lanczos methods uses a symmetric matrix, but it follows fromelementary algebra that this is no restriction. Although it was designed for real-valued
matrices, it applies to other fields, unless it encounters a vector orthogonal to itself. To
avoid self-orthogonal vectors, it is better to operate in an extension field rather thanGF (2) itself. Block variants [15, 16, 42] of both algorithms have been proposed totake advantage of word operations. The method currently in use in NFS factorization
experiments is Montgomery’s block Lanczos algorithm [42]: it requires n/(N − 0.76)
iterations where N is word size in bits. Each iteration applies the original matrix, as
well as its transpose, to an n × N matrix and performs a few additional operations,which we do not describe in detail. It should be pointed out that, at the moment,
none of the above algorithms can be massively distributed. This is a bottleneck for
future NFS factorizations, since the factor base will grow in size, thus leading to larger
matrices to be handled at the linear algebra stage.
3.4.5

Square root

Once the linear algebra stage has been performed, one needs to extract square rootsof huge algebraic numbers. Let γ be such an algebraic number in the number field
K = Q(α): γ is actually given as a large product of small algebraic numbers. The
first efficient method was found by Couveignes [20]: Couveignes noticed that, when
the degree d of the number field K is odd, there is a way to distinguish between√
the two square roots of a given number. This allows to compute γ using Chineseremaindering. However, Couveignes’s algorithm does not scale up to currently usedsizes. A major improvement was later found by Montgomery (see [40, 41, 22, 23, 44])and is the method used in recent NFS experiments. Computations show that therunning time is negligible compared to other stages of the NFS, such as sieving and11

linear algebra, even if no one currently knows how to prove the fact.
We sketch the basic principle of Montgomery’s algorithm and refer to [41, 22, 44]√
for details. The trick is to look for γ, as a large product of small algebraic numbers.
A priori, it is not clear that such a decomposition exists, and this is one of the reasons
why the complexity of Montgomery’s method is still unknown. The algorithm tries tofind a decomposition through an iterative process. Notice that the ideal factorization ofhγip
is completely known. Since γ is a square, we can thus obtain the ideal factorizationof hγi. At each step, the algorithm pselects a reasonably small integral ideal ineither the numerator or denominator of hγi, and uses lattice reduction to find an
appropriate algebraic integer within this ideal. Even though the small ideal is not ingeneral principal, it turns out that, in practice, it is possible to find an algebraic integer√
which is almost a generator, and which improves on the iterative approximation of γ.
√
After sufficiently many steps, one obtains a reasonably good approximation of γ, asa product of appropriate small algebraic integers obtained by lattice reduction. The
exact value of the error in the approximation can be found by Chinese remaindering.
√
Finally, a square root γ has been be computed.

3.5

Practical experiments

In practical terms, NFS beats QS for numbers of more than about 110 digits (see [22]).
The number field sieve was used to factor the 130-digit RSA challenge number in
april 1996, with an amount of computer time which was only a fraction of what wasspent on the old 129-digit QS-record. It was later used to factor RSA-140 in february
1999 with an amount of computer time about 2000 Mips-years. In august 1999, thefactorization of RSA-155 from the RSA list was obtained ([14]). The complete project
took seven calendar months. The polynomial selection took about one month on several
fast workstations. The sieving, was done on about 300 fast PCs and workstations
during 3.7 months. Filtering the relations and reducing the matrix corresponding
to these relations took one calendar month on an SGI Origin 2000 computer. The
block Lanczos step to find dependencies in this matrix took 224 CPU hours and 2
Gbytes of central memory on a Cray C916 supercomputer. The final square root step
was performed in about two days on an SGI Origin 2000 computer. The amount ofcomputer time spent on this new factoring world record is equivalent to 8000 mipsyears, whereas extrapolation based on RSA-140 and the asymptotic complexity formulafor NFS predicted approximately 14000 mips-years. As observed in section 3.4.2, thegain was caused by the improved polynomial search method.

12

bit-sizeof the modulus
512
1024
4096
6144
8192

complexity of NFS
in log2
63
85
155
182
206

Figure 1: Complexity of factoring

4

Consequences in terms of key sizes

4.1

The current status of factoring

The current status of factoring is well understood. The current record is still at 512
bits. However, factoring technology has spread out: another number of the same bitsize has been factored in October 2000, by a swedish team [2], in answer to a challenge
published in a book by Singh [55]. The experiment was carried through by a groupwhich did not consist of experts in the area, and, despite the fact that the running timethat they used was not optimal, they were successful. It is thus expected that larger
numbers will be soon factored, the main obstacle to a fully scalable implementation of
NFS being actually the linear algebra.

4.2

Selecting key sizes

In practical situations, the sizes of cryptographic keys based on the hardness of factoring
have to be chosen so that they outreach the expected performances of the factoringalgorithms, during the entire lifetime of the system. This involves making predictions.
The theoretical complexity of NFS Ln [1/3; c + o(1)], c ≈ 1.92, is a rough estimate,which is not of much use, for many reasons:• Due to memory constraints, the size of the factor base is always much less thanthe optimal choice that theory would dictate.
• Methods used in the implementations differ from those used in the complexity
analysis: the polynomial selection appears better in practical terms, while thelinear algebra is difficult to handle.
Still, a table of time estimates for the best known factoring method NFS, as shownon figure 1, can provide some indication. To derive an estimate of the key size corresponding to a given workload 2` , one searches for a modulus for which the righthand13

side is `. As a typical case, one can select a modulus of 1024 bits to provide a security
level over 280 .
In [14], the authors derive the following formulaY = 13.24D1/3 + 1928.6
for predicting the calendar year for factoring D-digit number by NFS. The same formulaappears in [9] and produces Y = 2018 for D = 309, i.e. for a 1024 bit modulus. Suchestimates should lead to immediately ban 768 bit moduli and to adopt 2048 bit moduli
for long-term security.
For moduli which are not of the form n = pq, for example for multiprime RSA
moduli, or for ESIGN moduli of the form p2 q, one should further take into account theresults in sections 3.1.3 and 3.2. Our findings is that lattice-based factoring cannot be athreat, if the repeated factor appears with exponent 2 , 3 or 4. Similarly, ECM remains
inefficient for moduli with three prime factors. For moduli with 4 prime factors, it islikely that they will be threatened by ECM before they are at hand for NFS, at least
for the minimal size 1024 bits. Accordingly, we do not recommend their use.

References[1] L. M. Adleman. Factoring numbers using singular integers, Proc. 23rd ACM
Symp. on Theory of Computation, 64–71, 1991.
[2] F. Almgren, G. Andersson, T. Granlund, L. Ivansson and S. Ulfberg. Singhchallenge 10.
http://wwwhome.cs.utwente.nl/ crypto/challenge-10.html[3] D. Atkins, M. Graff, A. K. Lenstra and P. Leyland. The magic words are squeeming
ossifrage, Proc. Asiacrypt’94, LNCS 917, (1995), 263–277.
[4] M. Bellare and P. Rogaway. Random Oracles Are Practical: a Paradigm for
Designing Efficient Protocols, Proc. 1st CCS, 62–73. ACM Press, New York,
1993.
[5] M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among Notionsof Security for Public-Key Encryption Schemes. Proc. Crypto ’98, LNCS 1462,
26–45. Springer-Verlag, Berlin, 1998.
[6] M. Bellare and P. Rogaway, Optimal asymmetric encryption - How to encryptwith RSA, Proc. Eurocrypt’94, LNCS 950, 1995, 92–111.
[7] D. Boneh, G. Durfee, and N. Howgrave-Graham. Factoring N = pr q for large r,
Proc. Crypto’99, LNCS 1666, 1999, 326–337.
14[8] D. Boneh and R. Venkatesan. Breaking RSA may not be equivalent to factoring,
Proc. Eurocrypt ’98, LNCS 1402, 59–71, Springer-Verlag, Berlin, 1998.
[9] R. P. Brent. Some Parallel Algorithms for Integer Factorisation, Euro-Par 99,
LNCS 1685, (1999), 1–22.
[10] J. P. Buhler, H. W. Lenstra, and Carl Pomerance. Factoring integers with thenumber field sieve, in [35], 50-94.
[11] R. Cramer and V. Shoup. Signature Schemes Based on the Strong RSA Assumption, 6th ACM Conference on Computer and Communication Security. ACM
Press, (1999), 46–51.
[12] S. Cavallar. Strategies for filtering in the Number Field Sieve, Algorithmic Number
Theory – Proc. ANTS-IV, LNCS 1838, Springer-Verlag, 2000.
[13] S. Cavallar, B. Dodson, A. K. Lenstra, P. Leyland, W. Lioen, P. L. Montgomery,B. Murphy, H. te Riele, and P. Zimmermann. Factorization of RSA-140 using thenumber field sieve, Proc. Asiacrypt ’99, LNCS 1716, Springer-Verlag, 1999.
[14] S. Cavallar, B. Dodson, A. K. Lenstra, W. Lioen, P. L. Montgomery, B. Murphy, H. te Riele, K. Aardal, J. Gilchrist, G. Guillerm, P. Leyland, J. Marchand,
F. Morain, A. Muffett, C. Putnam, C. Putnam, and P. Zimmermann. Factorizationof 512-bit RSA modulus, Proc. Eurocrypt ’00, LNCS 1807, 1–18, Springer-Verlag,
2000.
[15] D. Coppersmith. Solving linear equations over GF(2): block Lanczos algorithm,
Linear Algebra and its Applications, 192:33–60, 1993.
[16] D. Coppersmith. Solving linear equations over GF(2) via block Wiedemann algorithm, Math. Comp., 62:333–350, 1994.
[17] D. Coppersmith, Finding a Small Root of a Univariate Modular Equation, Proc.
Eurocrypt’96, LNCS 1070, 1996, 178–189.
[18] D. Coppersmith, Finding a Small Root of a Bivariate Integer Equation; Factoringwith High Bits Known, Proc. Eurocrypt’96, LNCS 1070, 1996, 178–189.
[19] D. Coppersmith. Small Solutions to Polynomial Equations, and Low Exponent
RSA Vulnerabilities, J. Cryptology, 10, 1997, 233–260.
[20] J.-M. Couveignes. Computing a square root for the number field sieve, in [35],
95–102 .

15[21] D. Dolev, C. Dwork, and M. Naor. Non-Malleable Cryptography, Proc. 23rd
STOC. ACM Press, New York, 1991.
[22] R.-M. Elkenbracht-Huizing. An implementation of the number field sieve. it Exp.
Math. 5, 1996, 231–253.
[23] M. Elkenbracht-Huizing. A multiple polynomial general number field sieve. Algorithmic Number Theory – Proc. ANTS-II, LNCS 1122, 101–116, Springer-Verlag,
1996.
[24] R.-M. Elkenbracht-Huizing. An implementation of the number field sieve, it Exp.
Math. 5, 1996, 231-253.
[25] NTT Corporation. ESIGN Specification, submission to CRYPTREC, September
2001.
[26] NTT Corporation. Self evaluation of ESIGN. Submission to CRYPTREC, September 2001.
[27] A. Fiat and A. Shamir. How to Prove Yourself: Practical Solutions of Identificationand Signature Problems, Proc. Crypto ’86, LNCS 263, 186–194. Springer-Verlag,
Berlin, 1987.
[28] E. Fujisaki, T. Okamoto, D. Pointcheval, and J. Stern. RSA–OAEP is Still Alive,
Cryptology ePrint Archive 2000/061, http://eprint.iacr.org/.
[29] A. Hildebrand and G. Tenenbaum. Integers without large prime factors, J. Théor.
Nombres Bordeaux, (5):411–484, 1993[30] N. Howgrave-Graham. Finding small roots of univariate modular equations revisited, Cryptography and Coding, LNCS 1355, 1997, 131–142.
[31] A. Joux and J. Stern. Lattice Reduction: a Toolbox for the Cryptanalyst, J.
Cryptology 11, 1998, 161–186[32] C. S. Jutla. On finding small solutions of modular multivariate polynomial equations, Proc. Eurocrypt ’98, LNCS 1233, 158–170.
[33] B. A. Lamacchia and A. M. Odlyzko. Solving large sparse systems over finite
fields, Proc. Crypto ’90, LNCS 537, Springer-Verlag, 1990.
[34] A. K. Lenstra, H. W. Lenstra and L. Lovász. Factoring polynomials with rationalcoefficients, Mathematische Ann., 261, (1982), 513–534.
[35] A. K. Lenstra and H. W. Lenstra, Jr. The Development of the Number Field Sieve,
Lecture Notes in Mathematics 1554, Springer-Verlag, 1993.
16

[36] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard. The number
field sieve, 11-42 in [35].
[37] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard. The factorization of the ninth Fermat number, Math. Comp., 61:319–349, 1993.
[38] A.K. Lenstra and E. Verheul. Selecting cryptographic key sizes, Proc. PKC’2000,
LNCS 1751, 446–465, 2000.
[39] N. Lygeros, M. Mizony, P. Zimmermann, A new ECM record with 54 digits,
http://www.desargues.univ-lyon1.fr/home/lygeros/Mensa/ecm54.html[40] P. L. Montgomery. Square roots of products of algebraic numbers. Walter
Gautschi, editor, Mathematics of Computation 1943-1993: a Half-Century ofComputational Mathematics, Proceedings of Symposia in Applied Mathematics,
567–571, American Mathematical Society, 1994.
[41] P. L. Montgomery. Square roots of products of algebraic numbers, Draft of June,
1995. Available at ftp://ftp.cwi.nl/pub/pmontgom/sqrt.ps.gz.
[42] P. L. Montgomery. A block Lanczos algorithm for finding dependencies over GF(2),Proc. Eurocrypt’95, LNCS 921, 1995, 106–120.
[43] B. Murphy. Modelling the yield of number field sieve polynomials, Algorithmic
Number Theory – Proc. ANTS-III, LNCS 1423, Springer-Verlag, 1998.
[44] P. Nguyen. A Montgomery-like square root for the number field sieve, Algorithmic
Number Theory – Proc. ANTS-III, LNCS 1423, Springer-Verlag, 1998.
[45] T. Okamoto, E. Fujisaki and H. Morita. TSH-ESIGN: Efficient Digital Signature
Scheme Using Trisection Size Hash. Submission to P1363a, 1998.
[46] D. Panario, X. Gourdon, and P. Flajolet. An analytic approach to smooth polynomials over finite fields, Algorithmic Number Theory – Proc. ANTS-III, LNCS
1423. Springer-Verlag, 1998.
[47] R. Peralta and E. Okamoto. Faster Factoring of Integers of a Special Form , IEICE
Transactions on Fundamentals of Electronics, Communications, and Computer
Sciences, v. E79-A, n.4 (1996), 489–493.
[48] J. Pollard. Monte Carlo methods for index computation mod p, Math. Comp.,
32, 918–924, 1978.
[49] J. M. Pollard. Factoring with cubic integers, in [35], 4–11.

17

[50] J. M. Pollard. The lattice sieve, in [35], 43–49.
[51] R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures
and Public Key Cryptosystems, Communications of the ACM, 21(2):120–126,
February 1978.
[52] R. L. Rivest, A. Shamir, L. M. Adleman. Cryptographic Communications System
and Method, US patent 4 405 829, September 20, 1983 (filed 14/12/1977).
[53] RSA Laboratories. Information on the RSA challenge,
http://www.rsa.com/rsalabs/html/challenges/html[54] RSA Laboratories. PKCS # 1 Version 2.1: RSA Cryptography Standard.
Draft, January 2001, http://www.rsa.com/rsalabs/pubs/PKCS/.
[55] S. Singh. The Code Book, 1999.
[56] T. Takagi. Fast RSA-Type Cryptosystem Modulo pk q, Proc. Crypto’98, LNCS
1462, (1998), 318-326.
[57] P.C. van Oorschot and M. J. Wiener. Parallel collision search with cryptanalytic
applications, J. Cryptology, 12, (1999), 1–28.
[58] D. H. Wiedemann. Solving sparse linear equations over finite fields. IEEE Trans.
Inform. Theory, 32:54–62, 1986.

18