Evaluation of Complexity ofMathematical Algorithms
Thorsten Kleinjung

1

Introduction

The security of many cryptographic applications bases on the difficulty of factoring
integers. One of the two major steps in the best factoring algorithm known so far isthe collection of relations. The purpose of this report is to estimate the cost of thisstep for integers of size 1536-bit and 2048-bit using existing software and hardware.
This will give an upper bound for the difficulty of this step.
The next section gives a brief overview of the factoring algorithm and a moredetailed description of the relation collection step. In section 3 we discuss the choiceof polynomial pairs which are a prerequisite for the collection of relations. The
main part of this report consists of the fourth section which describes the sieving
experiments, how parameters were chosen and how estimates were derived fromthe results of the experiments. Moreover, several improvements leading to better
estimates are discussed. The report concludes with a summary of the results.

2

The general number field sieveFirst, we give a brief overview of the General Number Field Sieve (GNFS) (see [LL])and fix the notation. Then we explain the collection of relations in more detail.
Let N be a composite number to be factored which is not a power of a prime.
We assume that N is not divisible by small primes, in particular not by auxiliary
primes which are used in the algorithm below. The GNFS algorithm consists of thefollowing five steps:
1. Polynomial selection
In this step two coprime, irreducible polynomials, f1 , f2 ∈ Z[X], are chosensuch that they share a common root m modulo N . Since the runtime of the1

subsequent steps depends on the quality of the chosen polynomial pair, many
pairs should be considered and the best one chosen (see also next section).
We denote by F1 , F2 ∈ Z[X, Y ] the corresponding homogeneous polynomials,) · Y deg(fi ) , i = 1, 2. Let also Ki = Q[X]/(fi (X)) bei. e., Fi (X, Y ) = fi ( XY
the associated number fields, Ki,(N ) = { xy |x, y ∈ OKi , gcd(y, N ) = 1} andφi : Ki,(N ) −→ Z/N Z defined by X 7→ m.
2. Collection of relations
The aim of this step is to find sufficiently many coprime pairs (a, b) ∈ Z × N
such that Fi (a, b) is Li -smooth for i = 1, 2, where L1 and L2 are parameters.
A number is said to be L-smooth if it splits completely into primes ≤ L. Eachpair (a, b) such that Fi (a, b) is Li -smooth, i = 1, 2, is called a relation and theparameters L1 and L2 are called large prime bounds.
The lattice sieving procedure to find such relations is described below in moredetail.
3. Construction of the matrix
This is a combination of several steps. First, duplicate relations, which forexample may arise by lattice sieving, are removed. Then a preliminary matrix
M0 over F2 is constructed whose rows resp. columns correspond to prime ideals
of norm ≤ Li in Ki , i = 1, 2, resp. to relations. The entry in a row corresponding
to the prime ideal Pi of Ki and a column corresponding to (a, b) is the valuation
modulo 2 of a − bX mod fi at Pi .
Next the matrix is preprocessed by eliminating zero rows, zero columns andcolumns containing a non-zero entry which is the only non-zero entry in its row.
Furthermore elementary column operations can be done. This preprocessing
results in a denser, but smaller matrix M whose rows correspond to prime
ideals of K1 or K2 and whose columns correspond to sets of relations.

4. Linear algebra
In this step some solutions of the linear system of equations M v = 0 over F2will be found. This is usually done by the block Lanczos or block Wiedemannalgorithm which usually give several (64, say) solutions.
5. Final computations
A solution Q
of M v = 0 corresponds to a subset S of the set of relations suchthat αi = (a,b)∈S a − bX mod fi , i = 1, 2, has an even valuation at almost
all prime ideals of Ki . Using quadratic characters one searches for a linear
combination of solutions of M v = 0 such that the corresponding αi are squares
2

in Ki (with very high probability). Then square roots βi2 = αi are calculated
and the computation of gcd(φ1 (β1 ) − φ2 (β2 ), N ) will heuristically split N withprobability ≥ 12 .
Heuristically the runtime of GNFS is
64

2

1

O(e(( 9 +o(1))(log N )(log log N ) ) 3 ).
Since this report only considers the second step (collection of relations) we now
present it in more detail.
There are several methods for finding relations, in practice one uses line sieving
and lattice sieving. For smaller numbers line sieving is faster than lattice sieving, but
for larger numbers (say, above 512 bit) only a small fraction of relations is usually
produced by line sieving. Therefore we focus on lattice sieving.
For i = 1, 2 let Fi be the set of prime ideals of degree 1 of Ki of norm lessthan some bound Bi < Li and whose norm is coprime to the discriminant and theleading coefficient of fi . These sets are called factor bases and their elements can be
represented by (p, X − r) where p is a prime number and r is a root of fi modulo p.
The numbers Bi are called factor base bounds.
In lattice sieving we first choose an ideal (q, X − s) of K1 called a special-q wheres is a root of f1 modulo q. For technical reasons we assume that q is square-free andcoprime to the discriminant and the leading coefficient of f1 .
For a special-q as above we consider pairs (a, b) such that a − bX ∈ (q, X − s).
This is done by choosing two vectors v and w which generate the lattice (q, X − s) ∩(Z ⊕ ZX). Then the sieving area Aq,s ⊂ Z2 consists of the pairs (a, b) corresponding
to iv + jw for −I ≤ i < I, 0 ≤ j < J. The vectors v and w are chosen in such a waythat the sizes of |F1 (a, b)| and |F2 (a, b)| become as small as possible.
A simplified description of lattice sieving is the following:
1. Initialize two arrays A1 and A2 each of size 2IJ with zero. The elements of Ak
correspond to (a, b) ∈ Aq,s and are denoted by Ak [(a, b)].
2. For each element (p, X − r) ∈ F1 add log p to A1 [(a, b)] if a ≡ br (mod p).
Optionally do analogous operations for small powers of p.
3. For each element (p, X − r) ∈ F2 add log p to A2 [(a, b)] if a ≡ br (mod p).
Optionally do analogous operations for small powers of p.
4. Identify all (a, b) such that Ak [(a, b)] ≥ log(|Fk (a, b)|) − tk for k = 1, 2 where
tk are parameters. The set of these (a, b) is called S.
3

5. For each (a, b) ∈ S compute Fk (a, b), do trial division up to Bk (this can use(a,b) (a,b)
information of the preceding steps) and find a splitting |Fk (a, b)| = Sk Rk
(a,b)
(a,b)
such that all prime factors of Sk are below Bk and all prime factors of Rk
are above Bk .
(a,b)

(a,b)

6. For each (a, b) ∈ S such that Rk ≤ Ck , k = 1, 2, try to factor Rk . The(a,b)
numbers Ck are parameters called cofactor bounds. If R1 is L1 -smooth and(a,b)
R2 is L2 -smooth output (a, b) as a relation.
The parameters tk should be adjusted to Ck , i. e., a little bit bigger than log Ck .

3

Polynomial selection

The aim of the polynomial selection step is to chose a polynomial pair which minimizes the total runtime. The time spent in collecting relations depends on thesmoothness properties of Fi (a, b), i = 1, 2, for typical values of (a, b). These smoothness properties heuristically depend on the size of |Fi (a, b)| and the number of roots
modulo small primes of fi . The size of |Fi (a, b)| depends on the degree of fi and thesize of its coefficients if the sizes of a and b are fixed. For given degrees of fi one
tries to find a polynomial pair whose coefficients are small and which has many roots
modulo small primes.
Except for one method, so far there are only methods which produce acceptable
polynomial pairs where one polynomial is linear. The exceptional method works only
for deg(f1 ) = deg(f2 ) = 2, and for larger numbers, at least for numbers larger than
512 bit, the polynomial pairs produced are worse
P than those of other methods.
Let deg(f1 ) = d > 1, deg(f2 ) = 1, f1 = di=0 ai X i and f2 = b1 X + b0 . In thefollowing we will call f1 algebraic polynomial and f2 rational polynomial and, moregenerally, refer to many quantities belonging to f1 resp. f2 as algebraic resp. rational.
The polynomial selection method we used (see [Mur] and [Kle]), has an outer loop
over ad , then a loop over suitable b1 for this ad and an inner loop over b0 . Moreover,ad should be divisible by many small primes and b1 should be a product of many
primes ≡ 1 (mod d).
For the 1536-bit number RSA-1536 (see [RSA]) we have chosen d = deg(f1 ) = 7
which seems to be better than degree six or eight. For the 2048-bit number RSA-2048
the degree f1 was also set to 7. The best polynomial pairs for these two numbers forvarious degrees and parameters used in their selection can be found in appendix A.
Now we try to estimate which improvement for the quality of the polynomial pair
we might get if a reasonable amount of time (e. g. 1 % of the total time) were spent for4polynomial selection. We assume that, spending one time unit for the selection, we
get on average one algebraic polynomial f1 with coefficient size c. Spending 2d+1 timeunits we heuristically should get on average one algebraic polynomial with coefficient
size 2c (assuming that the coefficients behave “randomly”). This is the expected
coefficient size for one time unit if the input number were 2d+1 times smaller. So
increasing the time for polynomial selection by a factor f has the same effect as
reducing the input number by a factor f . Thus the quality of the polynomial pair)should be improved by a factor TT ((Nwhere T (x) is the runtime to factor a numberN)fof size x. Since we consider a quotient of T we replace it by the function T0 defined
by
64

2

1

T0 (x) = e( 9 (log x)(log log x) ) 3 .
For RSA-1536 a reasonable polynomial selection effort would be about 246 times
longer than that used for this estimate. This would lead to an improvement of the1536 )≈ 2.5. For RSA-2048 a reasonable polynomial
total runtime by a factor TT00 (2(21490 )60
selection effort would be about 2 times longer which leads to an improvement by a(22048 )factor TT00 (21988 ) ≈ 2.8. Note that these arguments and estimates are very heuristic.

4

Estimating the sieving step

4.1

Estimating the number of relations

We first describe the general outline of sieving experiments and how we can estimate
the runtime of the complete sieving step.
In the sieving step we do lattice sieving for many special-q until the number of(unique) relations is sufficiently large for the subsequent matrix step. If the number ofrelations exceeds the sum of the number of prime ideals in Ki with norm less than Li ,i = 1, 2, by a small amount, this is sufficient. So we strive for approximately π(L1 ) +π(L2 ) relations where π(x) is the number of primes less than x. In factorizations ofsmaller numbers it is usually sufficient to collect less relations, say, 0.8·(π(L1 )+π(L2 ))relations. However, the parameters in this context differ much from those chosen
usually, such that we cannot rely on past experience. So we use the more conservative
bound π(L1 ) + π(L2 ).
The number of relations generated by one special-q depends mainly on the sizeof q and on the lengths and angle of the two vectors chosen in the lattice sieving
procedure for the special-q. The second dependence can probably be reduced byadapting the shape of the sieving area, but this is not done by the program used forthe experiments.
5

To estimate the number of (non-unique) relations for lattice sieving for a set
Q of special-q, we choose a smaller subset Q0 ⊂ Q, do lattice sieving for Q0 and
extrapolate the number of relations. In order to get a more precise estimate the subset
Q0 should be a “random” subset of Q. This can be done by ordering the special-q bysize and choosing every n-th special-q for some n. If the set Q consists of special-q
in an interval [q0 , q1 ] which are almost uniformly distributed over the interval, it is0convenient to choose special-q near the locations q0 + iw, i ∈ Z ∩ [0, q1 −q]. The widthw
w controls the accuracy of the estimate.
Since lattice sieving produces duplicate relations, we also need to estimate thenumber of duplicates. Let r1 , . . . , rk be k relations generated as described above.
For each ri we count the number ni of special-q in Q which would generate the same
relation ri if lattice sieving for this special-q were done with the same parameters.
This can be done easily since we get a list of candidates for special-q from thefactorizations of F1 (a, b) where (a, b) is the pair corresponding to ri . For each of thesecandidates we check whether (a, b) is in its sieving area and whether the bounds CjP
for cofactors are kept. Then the estimated fraction of unique relations is k1 ki=1 n1i .
For very large numbers like 1536-bit or 2048-bit numbers we may not be able togenerate a sufficient number of relations for an estimate, since the average time togenerate one relation might be several CPU days or CPU years. But we can keep
track of the (a, b) pairs whose cofactors are below the bounds Cj and compute theprobability that both cofactors are smooth. The sum of these probabilities is the
expected number of relations. How to compute these probabilities will be explained
in section 4.3.
Since we will generate only a few relations or even no relation, we cannot use
the procedure above to estimate the number of duplicates. Therefore we use the
Dickman ρ-function and some simplifications for getting an upper bound on thenumber of duplicates.
Let gi (x) be a function which roughly approximates the maximum of |Fi (a, b)|
where (a, b) ranges over a sieving area of size x. If, for example, the absolute size ofdeg(Fi )the coefficients of Fi is about c one may choose gi (x) = c · x 2 . Let nrel,q be thenumber of relations obtained from one special-q (q, X − s) (we suppress X − s in thefollowing) and let ndup,q,q0 be the number of relations obtained from q and from q 0 ,0i. e. , thenumberPof relations is
P number of duplicates between q and q . Then the1 P
nrel = q∈Q nrel,q and the number of duplicates is ndup ≤ 2 q∈Q q6=q0 ∈Q ndup,q,q0(≤ because some relations can arise from three or more special-q). We will nownapproximate nrel,q and ndup,q,q0 in such a way that the quotient ndup
heuristically onlyrel
increases.
Let A be the size of the sieving area for one special-q. The size of the intersection
6

0). The values ofof the sieving areas for q and q 0 is heuristically less than A·gcd(q,qmax(q,q 0 )0

qq
F1 (a, b) for (a, b) in this intersection are divisible by gcd(q,q0 ) . We now assume thatthe lattice siever finds all relations with F1 (a, b) being L1 -smooth and F2 (a, b) being
L2 -smooth. If we replace the value of |Fi (a, b)| by its maximum over all (a, b) of thesieving area, we get:
 


X
log g2 (qA)
log g1 (qA) − log qρnrel =Aρ
log
L
log L2
1
q∈Q

and
0

ndup

qq
log g1 (min(q, q 0 )A) − log gcd(q,q0)
1 X X A · gcd(q, q 0 )=ρ
02 q∈Q 0max(q, q )log L1
q6=q ∈Qlog g2 (min(q, q 0 )A)×ρ
.
log L2!

×

Replacing the value of |Fi (a, b)| by its maximum over all (a, b) should increase thensince the arguments of the ρ-function in the formula for ndup are notquotient ndup
rel

ρ(x)
bigger than the arguments in the formula for nrel and the function ρ(x+c), c > 0, isincreasing.
In our application the special-q consist of two prime factors, giving a fourfold
summation in the formula for ndup . This can be evaluated by grouping primes inintervals of the form [hn , hn+1 [, n ∈ N, for some h > 1 and approximating thenumber of primes in such an interval by the prime number theorem.
Note that heuristically the estimate for the fraction of duplicates is higher than
the actual fraction. But if we choose parameters in such a way that the estimatedfraction of duplicates is 21 , the error will be at most a factor 2.

4.2

Selecting parameters

In this section we describe the interdependence between various parameters of thelattice siever and how the parameters for the sieving experiments have been chosen.
The main restriction from hardware is limited memory. We mainly consider PCs
with 2 GB memory.
The lattice siever uses 20 byte per factor base element, 4 byte for the prime, 4
byte for its root, 4 byte for the current position in the sieving area and 8 byte fortwo vectors needed for calculating the position of the next sieving event. Moreover,some buffers whose sizes depend on the sizes of the factor bases and the size of the7

sieving area are necessary, but the total size of these buffers is usually smaller thanthat for the factor base data. For a PC with 2 GB memory this restricts the total
size of the factor bases to about 70 to 80 million elements. Since the values of F1 (a, b)
are bigger than those of F2 (a, b) for most of the sieving area, it is better to choose
the factor base bound B1 bigger than B2 . Therefore the values B1 = 11.5 · 108 and
B2 = 2.5 · 108 were chosen.
Asymptotically the factor base sizes grow like the square root of the runtime. If
costs of memory are not considered, optimal factor base sizes for a 200-digit number
require about 1 GB. Extrapolating this, using the function T0 of section 3, yields amemory size of about 60 TB for 1536-bit numbers (or 6 PB for 2048-bit numbers).
This is only a very rough estimate, not considering an actual implementation. Since
our factor base is much smaller than an optimal one, the number of relations ina given sieving area is much smaller than for an optimal factor base. One cancompensate this a bit by increasing the cofactoring bounds Ci which also increases
the time spent in the cofactorization step. This is discussed in the next section.
In lattice sieving the actual sieving phase for a special-q is preceded by a phase inwhich a transformation of coordinates has to be done for each factor base element.
If the sieving area is chosen too small, initialization costs will dominate the runtime.
So it should not be chosen too small.
Choosing a larger sieving area will reduce the number of special-q needed for generating enough relations. It also leads to less duplicates but to slightly higher values
Fi (a, b), thus less relations for a fixed number of (a, b) pairs. From factorizations ofsmaller numbers it seems to be better to use a sieving area which is not too big, so
we choose it to be of size 216 × 215 . Another reason for this choice is that the current
lattice sieving program cannot handle sieving areas of size above 231 .
For the number under consideration and the parameter choices above, the sizeof the largest special-q will be larger than the large prime bounds Li . So a relation
for a special-q will only be useful if at least two relations were generated for thisspecial-q. Since this will usually not be the case, we only consider composite specialq. To reduce the number of duplicates we restrict ourselves to special-q consisting ofexactly two prime factors and also set a bound pmin on the minimal size of the prime
factors.
For the large prime bounds Li we set L = L1 = L2 and extrapolate L fromcompleted factorizations of smaller numbers. Then pmin and the interval [qmin , qmax ]with qmax ≈ 2qmin for the special-q are chosen, such that the following two conditions
are satisfied:• The expected number of duplicates is less than 50%.
8• The expected number of relations is about 4π(L), π(x) being the number ofprimes less than x.
This would give us enough relations to complete the factorization if the sieving step
were carried out.

4.3

Cofactoring

Here we consider the problem of finding good strategies for doing the cofactoring.
We also discuss how to compute the expected cost and yield of a certain strategy.
In the following we will consider three factoring algorithms (see for example [Coh])for doing the cofactoring, namely the Multiple Polynomial Quadratic Sieve (MPQS),
Pollard’s p − 1 method and the Elliptic Curve Method (ECM). For the purposes ofcofactoring this selection of algorithms seems to be most appropriate.
MPQS is an algorithm which (heuristically) always factors the input number, andits runtime depends mainly on the size of the input number. The p − 1 algorithm
(p−1)
(p−1)
(p−1)
(p−1)
has additional parameters B1, B2∈ N. For fixed parameters B1, B2
this algorithm may or may not give a splitting of the input number. The probability
(p−1)
(p−1)
, B2
and the size of the prime factorsthat a number is split depends on B1
(p−1)
(p−1)
of this number. The runtime depends on the parameters B1, B2
and on thesize of the input number. The ECM algorithm behaves similarly with parameters(ECM )(ECM )B1, B2∈ N. It has an additional parameter E, an elliptic curve. When
carefully changing the elliptic curve E for ECM, the runtime and the probability of
splitting will not depend on E. The difference between p − 1 and ECM is that p − 1with fixed parameters will always find the same prime divisors, whereas ECM with
fixed parameters but a different E will find different prime divisors.
Using MPQS usually gives a complete factorization of the input number, butusing p − 1 or ECM only gives a splitting into smaller factors, possibly composite.
We make the following
Assumption: When a splitting of a cofactor has been found, the time to complete
the factorization is negligible.
This assumption will be discussed below.
We will call a factoring method one of the following three algorithms:• MPQS,(p−1)• p − 1 with fixed parameters B1(p−1)

and B2(ECM )• ECM with fixed parameters B1

9or(ECM )

and B2.

Note that ECM with different parameters will be considered as different factoring
methods. We say that a factoring methods F is applied to a number, if the number
is used as input for the algorithm F .
A finite sequence of factoring methods together with the information whether thefactoring method shall be applied to the algebraic or to the rational cofactor will becalled a strategy. For simplicity we assume that there are no two factoring methodsof type p − 1 which are applied to the same cofactor. Applying a strategy to a pairof cofactors shall mean that the factoring methods of the sequence are successively
applied to their respective target numbers, avoiding unnecessary work. This meansthat we abort if a prime factor > L is found and that a factoring method is skipped
if its target has already been split.
For i = 1, 2 and m > 1 let Mi (n; n1 , . . . , nm ), n1 ≤ n2 ≤ . . . ≤ nm be the numberof n-bit composites which have no prime divisor ≤ Bi and which are a product ofm prime numbers of size n1 , . . . , nm -bit. These numbers can be approximated using
the prime number theorem. For a fixed n there are only finitely many m-tuples(n1 , . . . , nm ) such that Mi (n; n1 , . . . , nm ) is non-zero. For simplicity we make theAssumption: The large prime bounds Li are exact powers of 2.
We call (n; n1 , . . . , nm ) Li -smooth if 2nk ≤ Li for k = 1, . . . , m.
To compute the cost cost(S; r1 , r2 ) and yield yield(S; r1 , r2 ) for a strategy S applied to a pair of cofactors of size r1 -bit and r2 -bit, we also need the (average)
runtimes of the factoring methods in the strategy and the probabilities that thesefactoring methods find an r-bit factor for r ≤ max(r1 , r2 ). We denote these data byc(F, n) for the cost for an n-bit input number and by p(F, r) for the probability tofind an r-bit prime factor where F is a factoring method. These data can be precomputed. Then the calculation of the cost and yield for a strategy S = (F Mj , sj ),j = 1, . . . , l, F Mj : factoring methods, sj ∈ {1, 2}, applied to a pair of cofactors ofsize r1 -bit and r2 -bit is done as follows:
1. Let ki be the number of non-zero Mi (ri ; n1 , . . . , nm ) for i = 1, 2. Initialize two arrays A1 and A2 of length k1 resp. k2 with the non-zero numbers
Mi (ri ; n1 , . . . , nm ). We refer to the entry of Ai containing Mi (ri ; n1 , . . . , nm ) asAi [n1 , . . . , nm ].
2. Let ai be the sum of the entries of Ai and a = a1 a2 . Set c ← 0, g1 ← 0 andg2 ← 0 (in the steps below c will be the cost up to that step and gi will be thenumber of smooth ri -bit cofactors detected up to that step).
3. For j = 1, . . . , l do the following:10

(a) Let bi be the sum of the elements of Ai . Set b3−sj ← b3−sj + g3−sj andb ← b1 b2 (b is the number of pairs of cofactors for which we do not know
at this point whether they are smooth or not).
(b) Set c ← c + b · c(F Mj , rsj ).

(c) Depending on the type of F Mj do:• MPQS: Set
g sj ← g sj +X

Asj [n1 , . . . , nm ](rsj ;n1 ,...,nm ) is Lsj -smoothand set all entries of Asj to zero.
• p − 1: For all entries Asj [n1 , . . . , nm ] of Asj compute
q=

m
Y

k=1

(1 − p(p − 1, nk )),add Asj [n1 , . . . , nm ] · (1 − q) to gsj if (rsj ; n1 , . . . , nm ) is Lsj -smoothand set Asj [n1 , . . . , nm ] ← Asj [n1 , . . . , nm ] · q.
• ECM: Analogous to p − 1, replacing p − 1 by ECM.
4. Set cost(S; r1 , r2 ) ← ac and yield(S; r1 , r2 ) ← g1ag2 .
For fixed bit sizes (r1 , r2 ) of the cofactors the procedure above can be used tocompute cost and yield for several strategies. To select the best of these strategies
one chooses a target rate t and selects the strategy S such thatyield(S; r1 , r2 ) − t · cost(S; r1 , r2 )is maximal for S. This is done for all (r1 , r2 ) and gives a collection of strategies
depending on t. In practice, the best t can be found by sieving experiments. In an
ideal situation t will be the quotient of the total yield by the total runtime.
For the calculation of the cost and the yield of a strategy we made the assumptionthat almost all of the time is spent in the first splitting of a cofactor. This assumption
is true for cofactors consisting of two prime factors. For cofactors consisting of
three prime factors the assumption also holds most of the time since the effort forfinding the first splitting is usually bigger than the subsequent splitting of the smaller
composite. However, for cofactors consisting of more than three prime factors theassumption seems to be no longer true. To reduce the time for subsequent splittings11

we use an ad hoc strategy consisting of ECM and MPQS such that the probability
that a smooth cofactor is not found is less than 10%. Using this ad hoc strategy
some relations may be missed, in the worst case 19%. Even with this ad hoc strategy,
for RSA-1536 twice as much time is spent for subsequent splittings as for the first
splitting (and for RSA-2048 the quotient is about 7).

4.4

Results

This section describes the results of the sieving experiments and gives estimates about
the complexity of the complete sieving step. A PC always refers to an Athlon64 CPU
with 2.2 GHz (or an Opteron) and the specified amount of memory (see appendix B
for technical data of the PCs used in the sieving experiments).
The sieving experiments were conducted as described in the previous sections:for a small, uniformly distributed subset of special-q lattice sieving was done and the
expected yield was obtained by summing up smoothness probabilities. Also the timespent by the sieving program was measured. We summarize the main restrictions
for the choice of parameters:• The set of special-q is chosen such that the expected fraction of duplicates willbe less than 21 .
• The expected number of relations shall be at least 4π(L).
• The expected number of relations is obtained as 0.81 multiplied by the sumof the smoothness probabilities of cofactor pairs passing the cofactor bounds
Ci (0.81 is a lower bound on the probability that a smooth pair of cofactors is
detected if both cofactors are split).
From the expected yield and the time measurements of the sieving experiments one
can compute the number of PCs needed to complete the collection of relations within
one year.
For RSA-1536 two sets of parameters were chosen, one for PCs with 2 GB ofmemory and one for PCs with 3.5 GB of memory. In the second variant the factor
base bounds are roughly twice as large as in the first variant. There is a limitation of
231 for factor base bounds, so the algebraic factor base bound in the second variant
was set to 2147480000.
The parameters were as follows:12

(B1 , B2 )(L1 , L2 )(C1 , C2 )[qmin , qmax ]pmin# special-q

variant 1(11.5 · 108 , 2.5 · 108 )(250 , 250 )(2320 , 2240 )[1 · 1020 , 1.85 · 1020 ]227 ≈ 1.3 · 108≈ 71.9 · 1016

variant 2(≈ 21.5 · 108 , 5 · 108 )(250 , 250 )(2320 , 2240 )[0.9 · 1020 , 1.65 · 1020 ]227 ≈ 1.3 · 108≈ 62.9 · 1016

The sieving experiment gave the following result:time per special-q
relations per special-q
necessary number of special-q
number of PC years

variant 1
variant 2
207.8 s212.9 s0.00023863 · 0.81 0.0002693 · 0.81
69.4 · 1016
61.5 · 1016
4.6 · 1012
4.2 · 1012

For RSA-2048 the following parameters were used for the sieving experiment for
PCs with 2 GB memory:(B1 , B2 )(L1 , L2 )(C1 , C2 )[qmin , qmax ]pmin# special-q(11.5 · 108 , 2.5 · 108 )(257 , 257 )(2400 , 2260 )[9 · 1024 , 15 · 1024 ]235 ≈ 340 · 108≈ 335 · 1020

The sieving experiment gave the following result:time per special-q
relations per special-q
necessary number of special-q
number of PC years

4.5

245 s
59 · 10−8 · 0.81
315 · 1020
25 · 1016

Possible improvements

In this section we discuss possible improvements. Algorithmic improvements or theuse of special purpose hardware are not considered.
First of all, in the estimates above some partial estimates were quite conservative:• Spending more time for the selection of polynomial pairs will very probably
give an improvement, heuristically of a factor 2 or 3 (see section 3).
13• The estimate for the fraction of duplicates is quite pessimistic. By generatinga few thousand relations (which already takes about 100 CPU years for RSA1536) one can get a better estimate. However, since the fraction of duplicatesis at most 50%, the improvement will be less than a factor 2.
• In factorizations of smaller numbers it is usually sufficient to generate about
1.6π(L) relations. If this is also true for the numbers and parameters describedabove, this will give an improvement by a factor 1.25.
• A more careful analysis of cofactoring strategies, also addressing the problem ofsubsequent splittings (see section 4.3), will probably improve the performance.
The gain of such an improvement is difficult to estimate, but it seems to beless than a factor 4.
• In general, one can search for better parameters. In this estimate the parameters were chosen with the conservative estimates (see above) in mind. If oneof the previous points leads to an improvement, a better choice of parameters
will probably give another improvement.
Next, there are some improvements by changing parameters:• Sieving over prime special-q below L = 250 resp. L = 257 and increasing thesieving area per special-q might reduce the number of duplicates. However, theaverage size of |Fi (a, b)| might increase. Moreover, the lattice sieving program
has to be adapted to this situation and there are some technical problems
which might reduce the performance of the sieving program. Hence it is notclear whether this will give an improvement.
• One might also collect relations where a few prime factors of the factorizations
of |Fi (a, b)| are bigger than L. This is usually only a small extra effort. By
combining the additional relations generated in this way into L-smooth relations a big fraction of the sieving time might be saved. However, it is difficult
to estimate the number of relations needed.
The main restriction for the experiments in this report is the limited amountof memory and the limitations of the software (the factor base bounds have to be
below 231 and the maximal size of the sieving area is 231 ). Here we circumvented the
problem of small memory by spending more time in cofactoring. However, there areother possibilities:14• One could use a hard disk to increase the amount of memory. In this casemost of the factor base information will be stored on the hard disk. Accessingthese information will be slow but still faster than generating them on thefly (generating a table of primes and computing the roots of Fi modulo theseprimes). However, using a hard disk seems to be slower than the next approach.
• One could use a parallelized lattice siever, distributing the factor base elements
among the nodes. Each node generates sieving events for the part of prime
ideals residing on the node and sends the events to their destination node. For
this approach fast communication between the nodes might be very important.
The approach seems to be suitable for multi-core processors.
The effect of increasing the available memory is hard to estimate without doing
sieving experiments. Therefore the following should be considered more as a guessthan an estimate.
For RSA-1536 we increase the factor base bounds to B1 = 16 · 1012 and B2 =4 · 1012 , keep the large prime bounds at L1 = L2 = 250 and set the cofactor bounds to
C1 = C2 = 2150 . The sieving area size will be increased to 223 × 222 and the specialq will be chosen as prime numbers near 60 · 1012 . Using the Dickman ρ-function
and integrating smoothness probabilities we estimate that about 32 relations are
generated per special-q. We think that this yield is sufficient since there are lessduplicates when using prime special-q and since the parameters are not exceptional,
thus less than π(L1 ) + π(L2 ) relations should be sufficient. Comparing the number ofrelations per sieving area and taking into account that we should have less duplicates,
we estimate that the size of the total sieving area has decreased by a factor 10 to 15.
The time per area will change in two ways. First, for this variant with smaller
cofactor bounds there will be less time spent in cofactoring, probably giving a speedup by a factor 2. Second, much more time is spent in the sieving part since thefactor bases are much bigger. Here the factor is harder to estimate since many
implementation specific details and probably also the cache structure play a role.
We optimistically assume that the factor is 2 so that it cancels the other 2 above.
In summary we guess that one might gain a factor 10 to 15 by providing enoughmemory. If the memory is made available via a network (parallelized siever), one has
to take communication costs into account, so the factor is smaller. For RSA-2048
similar arguments give a factor 20 to 30.

15

5Summary

From the sieving experiments described in this report one can derive several estimates
for the complexity of the relation collection step for 1536-bit and 2048-bit numbers.
The first variant called “upper bound” is a pessimistic estimate which makes quite
conservative assumptions at several points. By considering improvements from areasonable time for polynomial selection and taking into account another factor 2
for several improvements described at the beginning of section 4.5, we get the next
variant. Finally, we consider an optimistic variant in which we assume that a parallelsiever is available which improves the performance by a factor 10 for RSA-1536
resp. 20 for RSA-2048 (see the last part of the previous section). Moreover, theimprovements from polynomial selection are assumed in this variant.
The number of PCs needed to complete the collection of relations within one year
for these three variants is as follows:variant
RSA-1536 RSA-2048
upper bound
4.6 · 1012
25 · 1016
improved upper bound 0.92 · 1012 4.4 · 1016
parallel siever
0.18 · 1012 0.4 · 1016

Notice that these estimates are not lower bounds for the complexity since improved implementations, a better understanding of the involved parameters or algorithmic improvements can lower them further.

References[Coh] H. Cohen, A Course in Computational Algebraic Number Theory, GTM 138,
Springer, 1993.
[Kle] T. Kleinjung, On Polynomial Selection for the General Number Field Sieve,
Mathematics of Computation 76, 2006, p. 2037-2047.
[LL]

A. K. Lenstra and H. W. Lenstra, Jr. (eds.), The Development of the
Number Field Sieve, Lecture Notes in Math. 1554, Springer, 1993.

[Mur] B. A. Murphy, Polynomial selection for the Number Field Sieve Integer Factorization Algorithm, PhD thesis, The Australian National University, 1999.
[RSA] RSA Challenge, see
http://www.rsasecurity.com/rsalabs/challenges/factoring/index.
html
16

6

Appendix A: Polynomial pairs

For the 1536-bit number RSA-1536 polynomial pairs have been selected for degrees
d = deg(f1 ) = 6, d = 7 and d = 8. Comparing the yield of the best polynomial pairs
for each degree, it seems that d = 7 is optimal for this number. For the 2048-bit
number RSA-2048 polynomial selection was done for degrees d = 7 and d = 8. For
the sieving parameters used in this report degree d = 7 seems to be better.
The best polynomial pairs for these numbers and degrees are listed below. Moreover, some parameters of the polynomial selection are given, namely• the search interval for the leading coefficient ad of f1• the multiplier µ for ad , i. e., the search was restricted to leading coefficients ad
which are divisible by µ
• the number k of prime factors of the leading coefficient b1 of f2 .
Notice that not all ad of the search interval divisible by µ have been considered, but
only sufficiently many for a one day search on an 1 GHz Pentium III.
RSA-1536, d = 6:
intervalµ
k[1044 , 1044 + 1020 ]18410000400 = 24 · 32 · 52 · 11 · 17 · 23 · 29 · 41
18

f1 =

100000000000000000000000000000363596066133200x 6+1371130679310713476146228966182622548653848612762130x 5−5707666179610643646873375614374353204481891860037461369533x 4−160963700087271125174143126487276598418412474435870529672688061x 3+164447819456847231707809587430744544151941645379810374287951485299879x 2+1269510738072616118107413180835672278026807606577022829294041326844917810x−6173484915988502033881874600003769824218617629575447597734439226189766539803

f2 =26990842768180257376469739873247834685073761353x−5141682217651853177521549768125122593221948973547321520298700609576629

RSA-1536, d = 7:17intervalµ
k[1036 , 1036 + 1020 ]
26771144400 = 24 · 32 · 52 · 7 · 11 · 13 · 17 · 19 · 23
16

f1 = 1000000000000000037811142945142568000x 7−43714365350271595218854107295531451599556144x 6+30328754671516292832035468235744202558674475901616x 5−2549632694806349159734389882357104975174959388666079090x 4−7434766214490707054261180439521079108132968739472265699676x 3+26941031676370465249694738904702978153213780731967578381868353x 2+45868218740012733930559584256165992747756385156566775760747640786x−48867794882451008441424264335735273573088241264624142804371580106080
f2 = 205334469089201645309341276310576122905417473x−7856571290567634945150691614513931635402668625054838502550321
RSA-1536, d = 8:intervalµ
k[1029 , 1029 + 1020 ]45668422800 = 24 · 32 · 52 · 7 · 11 · 13 · 19 · 23 · 29
14

f1 = 100000000000551052285480396800x8−10133393169528506828230951011910791890x 7+901780358656075872817255177277099971864270x 6−90670288442378609588775438946496267530632299554x 5−14334835794374205526039536016358975462728310458682x 4+358310617791323589366857177202361127822082005574134492x 3+33110049713110545850285079729845420467697187173359266424x 2−287370915230875760619676359523492607060585447279920572374485x−13247690058366184312071837499390054778589967338871871964338425
f2 = 83789197455899997719224801544797105273x−1439888701649711975751878907534666702027882878032197802
18

RSA-2048, d = 7:[1056 , 1056 + 1020 ]
26771144400 = 24 · 32 · 52 · 7 · 11 · 13 · 17 · 19 · 23
16

intervalµ
k
f1 =100000000000000000000000000000000000073338147424598156000x 7+8395882633588606238472583967532001708930835342294610074799259311x 6−1624323846587182617948662934734932766459757587817030957853256978619586x 5−1629792266744980170101888726089171334493378868821693528092987281939755424x 4+33842219052921654312275628323473891052030445427581764495124943311088430533903x 3+97169126397510065827694983318278224750173367414888014525694202469140892668968x 2−127658905721988738113694551290560677881909461129950694195199704883206539032920354252x+70780743244066711466692928940077321828000766324763392134444939614936295115875125481344

f2 =41123412601722865693107152959526055267629x−114112405465044179083292898071688380999575821246316812608380320780980683979836071

RSA-2048, d = 8:intervalµ
k
f1 =[1046 , 1046 + 1020 ]45668422800 = 24 · 32 · 52 · 7 · 11 · 13 · 19 · 23 · 29
14
10000000000000000000000000001981831814793220400x 8−2215229217222143068192667641819120750038383822406401934x 7+1916609233552143409556906696947976221293415432294637458335663x 6+26661673829180097195647792070006982037560728914378888764588753212x 5−12568046072026764843056899895602077720675191153736607209110181686531x 4−30332231701156503137832844039609655625808443207936237027382905221701472x 3+8778624409291627225152939964712907763932508250115493296758218503675017729x 2+6961788354987745425831896013640880258326538241398055955063097842881660090004x−756525676219717966880555107720645406038893474949813849975176062414350072004951

f2 =3227909437146378332398639843301233073x−199602626981280818393607284895114464259910689488947173899674283165812114

19

7

Appendix B: Technical data of the PC

Below are listed some technical data of the PCs used for the sieving experiments.
CPU
Clock rate
L2 cache size
MemoryMemory size
Mainboard

AMD Athlon(tm) 64 X2 Dual Core Processor 4200+
2.2 GHz512 kB
DDR2 533 MHz
4 GB (3.5 GB available)
Asus M2N-VM

20