— Summary —Evaluation of complexity of the sieving step of thegeneral number field sieve
Thorsten Kleinjung and Arjen K. Lenstra
EPFL IC LACAL, Station 14, CH-1015 Lausanne, Switzerland

December 5, 2018
It will be apparent from our estimates, achieved using the best technologies available (aspublished in the open domain), that breaking even the least secure of commonly usedpublic keys, namely 1024-bit RSA moduli, requires an effort of well over a million core
years. A cryptanalytic effort of that magnitude is out of reach of the type of academic
projects that have, over the years, helped shape the public perception of the level of security
offered by public key cryptosystems. Obviously, these figures depend on the hardware andimplementations that we used and will change over time.
Breaking 1536-bit RSA moduli can be estimated to be at least five order of magnitude
more difficult, in accordance with theoretical estimates, and 2048-bit RSA moduli are,most likely, yet at least four orders of magnitude harder to break — but obtaining truly
reliable evidence for the latter estimate requires hardware that we do not have at our
disposal and do not even expect to get access to within the next decade.
Radically new insights are required to change these estimated efforts. As mentioned above
innovative ideas have been unusually scarce lately and it would be fair to say that theregular, extrapolation-based rate of cryptanalytic progress as assumed for instance in [2,1],
simply turned out to be overly optimistic.

References
1. A. K. Lenstra. Unbelievable security: Matching AES security using public key systems. In C. Boyd, editor,
ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer Science, pages 67–86. Springer, Heidelberg,
2001.
2. A. K. Lenstra and E. R. Verheul. Selecting cryptographic key sizes. Journal of Cryptology, 14(4):255–293, 2001.

Evaluation of complexity of the sieving step of thegeneral number field sieve
Thorsten Kleinjung and Arjen K. Lenstra
EPFL IC LACAL, Station 14, CH-1015 Lausanne, Switzerland

December 5, 2018

1

Introduction

The present introduction consists of four parts: a first part discussing technical trends forthe past 10 years that are related to integer factorization; a second part discussing recent
technical trends in related fields, in particular pertaining to newly emerging trends in publickey cryptography; a third part consisting of a brief summary of our findings, which canalso be found on the separately provided “Summary” page; and a final part describing thestructure of the remainder of the report.
Technical trends for the past 10 years related to integer factorization. Looking
at the developments in the field of integer factorization, at this point in time we areexperiencing the longest record-less drought since general purpose integer factoring became
relevant for cryptology [16,15]. Not only does the current 768-bit record [8]? date back to
December 2009, also we are not aware of efforts that are underway and that would breakthis record in a meaningful manner. Since the 768-bit record there has been an almost
total lack of new insights that would be worth an exhaustive testing effort, implying thatembarking on a huge calculation just for the sake of a new record given the current stateof the art would prove little more than the contributors’ persistence?? — while one may
doubt if it is the best way to spend one’s resources. Indeed, the current state of affairs does
not even measure up to the bleak estimate of future cryptanalytic abilities in [2].
In particular it is noted that since the publication of [14] in 2003 there has been a total lackof new trends that could affect the sieving step of the general number field sieve method for
integer factorization [10] or any other sieving based factorization method. Neither has there
been, during the past 10 years, any other technical trend that could have an important effecton the general number field method for integer factorization; the effects of new findings
reported in [6] and [12] must be considered to be relatively minor and the factorization
related work reported in [7] has no noticeable effect on the general number field sieve.
?

In this note we restrict ourselves to results that have been reported in the open literature and to computational
efforts that can be supported by ordinary, open domain, academic resources.
??
Maintaining interest in a huge effort is not easy: the large scale effort announced in [1], not involving factoring
but elliptic curve discrete logarithms, has not been completed yet. We have not been able to ascertain if the
project has been abandoned or not.

Concerning hardware trends, clock speeds and memory sizes have only developed at a very
modest pace during the last decade, and have thus had little or no influence on the sieving
step of the general number field sieve or its computational feasibility.
Recent technical trends pertaining to public key cryptography. This lack ofprogress in integer factorization does not imply that crypto-researchers relaxedly sit back,while feeling confident that information protection schemes based on 1024-bit RSA are
not vulnerable to open domain, academic factorization efforts within the foreseeable future, as it used to be the case since the invention of RSA. Quite on the contrary, due toa technological development that started many years ago and that may well turn out toremain as hypothetical as it has always been — and currently still is — many cryptopractitioners are worried about the security of their current schemes and are encouraging
the research community to devote its efforts to post-quantum cryptography. In particularsince the United States’ National Institute of Standards and Technology announced its
post-quantum crypto standardization initiative, this new trend has picked up considerable
steam, to the extent that interest in systems that are actually used and their cryptanalysis
receives less attention than it used to get.
Obviously, the hypothetical development that we are referring to is the fear, concern,or hope that it will, some time in the future, be possible to build a quantum computerthat is large enough to solve cryptanalytic problems (such as cracking 1024-bit RSA keys)
that are currently out of reach for non-hypothetical, existing hardware and realistic open
domain resource management. Given the considerable number of reputable scientists thatoccupy themselves with the many problems involved, the possibility that such a device
will indeed be realized cannot be outrightly dismissed. The subject has managed to collectsubstantial amounts of funding from a wide variety of agencies and corporations worldwide,and progress on many different fronts is reported frequently. To an outsider it is impossible
to assess how close we are getting to a quantum computer as a result of these developments,
if it were not for the estimate that is not infrequently made in press releases and otherpublications, namely that it will be at least another decade to turn the latest progress
into a working product: this was the case in the 1990s, in the 2000s, in the 2010s, and thesame number is still reported right now. Extrapolation of these announced developments
does not bode well for actual quantum computing anytime. A newer, related trend is theappearance of articles that express serious, (at least seemingly) well-argued doubts thatcryptanalytically capable quantum devices can ever exist; it should be noted, however,that there is only a trickle of naysayer skepticism [3,4] compared to the abundance of“good news”.
The present authors are not qualified to contribute a useful opinion to the quantum debate.
But it seems clear that adopting post-quantum cryptography anytime soon may not be themost urgent priority and may — or will — lead to undue risks. At the same time, being
up-to-date on the security of traditional cryptosystems remains as important as it used tobe, and this will be the case for many years to come. The present note contributes to the2security assessment of traditional public key cryptosystems by providing estimates for theeffort required to break RSA keys of various relevant sizes.
Summary of our findings. It will be apparent from our estimates, achieved using thebest technologies available (as published in the open domain), that breaking even the least
secure of commonly used public keys, namely 1024-bit RSA moduli, requires an effort ofwell over a million core years. A cryptanalytic effort of that magnitude is out of reach of
the type of academic projects that have, over the years, helped shape the public perceptionof the level of security offered by public key cryptosystems. Obviously, these figures dependon the hardware and implementations that we used and will change over time.
Breaking 1536-bit RSA moduli can be estimated to be at least five order of magnitude
more difficult, in accordance with theoretical estimates, and 2048-bit RSA moduli are,most likely, yet at least four orders of magnitude harder to break — but obtaining truly
reliable evidence for the latter estimate requires hardware that we do not have at our
disposal and do not even expect to get access to within the next decade.
Radically new insights are required to change these estimated efforts. As mentioned above
innovative ideas have been unusually scarce lately and it would be fair to say that theregular, extrapolation-based rate of cryptanalytic progress as assumed for instance in [11,9],
simply turned out to be overly optimistic.
Report organization. This report is organized in the following manner. Section 2 contains
a high level description of the best — to our knowledge — cryptanalytic tool that we haveat our disposal to assess the security of RSA moduli, namely the general number field sieve
method for integer factorization. Two specific steps of the number field sieve that play a
prominent role for our analyses are explained at the level of details required to be able
to fully understand our approach and, if required, to re-derive our results; these are thesieving step and the cofactoring step. The details of the assessment method that we used,and how we arrived at the optimal overall estimates for a successful cryptanalytic effort,
are described in Section 3 for 768-, 1024-, and 1536-bit composites. The actual resultsof our experiments, for the three sizes just mentioned but also for the 2048-bit case, arereported in Section 4; for the 2048-bit case this includes a description of our assessment
methodology. Background data are provided in the appendices.
Comments on the other steps of the number field sieve integer factorization method are
explicitly not included in this report, as the other main step, the linear algebra step,would require more resources than accessible to us in terms of memory and communication
networks. All other steps are less critical.

2

Review

This section contains a brief review of some basic material of the previous report [5],namely of the number field sieve [10], of its sieving step and finally of the cofactoring step,a substep of the sieving step.
3

2.1

The number field sieve

Let N be an integer which is neither a power of a prime nor divisible by small primes, small
depending on the parameters chosen in the algorithm. The number field sieve attempts tofactor N by performing the following five steps:
1. Polynomial selection
Two coprime polynomials f1 , f2 ∈ Z[x] are chosen such that they share a root m modulo N and such that for each of the two polynomials its coefficients are coprime. The
corresponding homogeneous polynomials are denoted F1 , F2 ∈ Z[x, y], i.e., Fi (x, y) =fi ( xy ) · y deg(fi ) , i = 1, 2. Moreover, let Ki = Q[x]/(fi ), i = 1, 2, denote the associatednumber fields.
2. Collection of relations (or sieving step)In this step sufficiently many coprime pairs (a, b) ∈ Z × Z>0 are found such that Fi (a, b)
is Li -smooth (i.e., splits into primes ≤ Li ) for i = 1, 2. These pairs are called relations
and the integers Li are called large prime bounds or smoothness bounds.
3. Construction of the matrix
Since the previous step might produce duplicate relations, usually as a result of thelattice sieving technique (cf. below), these duplicates are removed in a first phase. The
set of unique relations gives rise to a matrix over F2 whose rows correspond to (most)prime ideals of norm at most Li in the number field Ki and whose columns correspondto these unique relations; the entries in the column associated to (a, b) are the valuations
modulo 2 at a prime ideal of a − bx in the corresponding Ki . Preprocessing this matrix
by elementary column operations and deleting zero rows or columns leads to a smaller
matrix M whose columns now correspond to sets of relations.
4. Linear algebra
Several solutions of the system of linear equations M v = 0 are computed in this step.
5. Final computation
A subspace of the vector space of solutions from the previous step is calculated suchthat each element of the subspace gives rise to a congruence c21 ≡ c22 (mod N ) whichleads to a possibly non-trivial splitting of N by computing gcd(c1 + c2 , N ).
α

1−α

Let LN [α, c] = e(c+o(1))(log N ) (log log N )for α, c ∈ R and 0 ≤ α ≤ 1. If the polynomials
qin

the first step are chosen appropriately, the large prime bounds are chosen as LN [ 31 , 3 89 ]q
and the relations (a, b) are collected for a and b bounded by LN [ 13 , 3 89 ] then the runningq
1 3 64time of the number field sieve is heuristically LN [ 3 , 9 ].
2.2

The sieving step

The goal of this step is to find sufficiently many coprime pairs (a, b) such that Fi (a, b) is
Li -smooth for both i = 1 and i = 2. In most situations the most efficient algorithm for4carrying out this task is lattice sieving. For a prime ideal q of OK1 which is unramified,of degree 1 and does not divide the leading coefficient of f1 , the set of pairs (a, b) suchthat (a − bx) is contained in q forms a lattice of covolume q where q is the norm of q.
For each pair (a, b) in this lattice F1 (a, b) is divisible by q. In lattice sieving one chooses a
range for q, e.g., an interval [q0 , q1 ], and examines for each prime ideal q as above a region
consisting of A points in the associated lattice, checking whether F1 (a, b) and F2 (a, b) areboth smooth. The prime ideal q is called a special q and the region is called the sieving
region. Notice that the primality of q is not needed since the above considerations also
apply to ideals which are a product of prime ideals satisfying the conditions above; below
such composite special q are used in the 2048-bit case.
The smoothness tests are usually carried out as follows. Let Bi , i = 1, 2, be positive integers
with Bi < Li and B1 < q0 (or at least B1 < q for the special q under consideration), and let(a,b) (a,b)(a,b)|Fi (a, b)| = Si Ri be the decomposition where the prime factors of Si
are at most Bi(a,b)
and the prime factors of Ri are all larger than Bi . A sieving procedure roughly analogous
to the sieve of Eratosthenes allows to determine (most of) the (a, b) in the sieving region for(a,b)
which both Ri , i = 1, 2, are below given bounds. This is done by identifying for (almost)each degree-1 prime ideal of OK1 resp. OK2 with norm at most B1 resp. B2 the set of pairs(a, b) of the sieving region which are contained in the prime ideal, and reorganizing this(a,b)
information in order to estimate the size of Si . The set of these prime ideals is called
the factor base and the bounds Bi , i = 1, 2, are called the factor base bounds. In a second(a,b)
phase it is checked for each of these candidates whether Ri
is Li -smooth for i = 1 andfor i = 2; this latter phase is called the cofactoring step.
2.3

The cofactoring stepIn the second phase of the sieving step, the cofactoring step, for i = 1, 2 integers Ri thatare free of factors ≤ Bi have to be tested for Li -smoothness. First, if either Ri -value isgreater than Li and cannot be proved to be composite using a probabilistic compositenesstest (with base 2), then the pair (R1 , R2 ) is discarded as probably not smooth. For eachremaining pair (R1 , R2 ) the smoothness tests are done in a two-stage process: a first stage
consisting of a factoring attempt of the Ri -values for i = 1, 2 that are composite but not
yet known to be Li -smooth (thus larger than Bi Li ) and a second stage that aims to findthe full factorizations of the pairs that (possibly as a result of the first stage) are known tobe smooth or for which a non-trivial factor has been found (in the first stage) for each Ri
that is not yet known to be Li -smooth. It should be noted that variations have been used
where the stages are intertwined.
In the first stage:– depending on the sizes of R1 and R2 a particular sequence of factoring methods isapplied to not already known to be smooth R1 or R2 (the factoring methods used are
Pollard’s p − 1 method, the elliptic curve method (ECM), and multiple polynomial
quadratic sieve (MPQS); the sequence is determined as explained further below);5

– if a non-trivial factor of Ri is found, further first stage Ri factoring attempts are skipped;– if Ri is found not to be Li -smooth (because a prime factor larger than Li is found),then the smoothness test for the pair (R1 , R2 ) fails and the pair (R1 , R2 ) is discarded.
If at the end of the first stage an Ri remains that is not known to be Li -smooth and thathas not been successfully factored in the first stage, then the pair (R1 , R2 ) is discarded
as being too hard to factor. Otherwise, in the second stage, a combination of ECM and
MPQS is attempted to factor all sufficiently small remaining composite parts of R1 and R2 .
If found to be not Li -smooth then the pair (R1 , R2 ) is discarded as not being smooth, if
not fully factored, then it is discarded as being too hard to factor.
Given the sizes, the smoothness probability of the pair (R1 , R2 ) can be approximated (usingthat the prime factors of Ri are larger than Bi for i = 1, 2 because the pairs (R1 , R2 ) were
found in the sieving step), along with the success probability and average running time of
the first stage (depending on the applicable sequence). The second stage is less amenable
to a precise analysis: all we can say is that in the second stage the parameters are chosen
in such a way that a smooth Ri is factored with a probability of at least 0.9. As in theprevious report this implies that in the second stage a smooth pair will be fully factoredwith probability at least 0.81.
The sequence of factoring methods to be used in the first stage is created by comparing
many sequences for each relevant pair of bit-lengths of the composites R1 and R2 . For eachpair of bit-lengths the sequence is chosen for which the ratio of the approximated running
time and success probability fits best the targeted number of seconds to be spent per
relation. An indication for the latter is given by the parameter r, with larger r indicatingthat more time may be spent in the cofactoring step. For some bit-lengths the resulting
sequence may be empty because the ratio is too large for all sequences considered.

3

General procedure

Since even for the smallest considered integer completing the sieving step takes a lot oftime, the estimates in this report are obtained by executing a small but representative
fraction of the sieving step and extrapolating the results. As in the previous report asieving step is considered to be complete when the number of unique relations is at least
2π(L) where L = L1 = L2 is the smoothness bound and π(x) is the number of primes
up to x. Since lattice sieving usually will produce duplicate relations, i.e., relations foundfor several different special q-values, these have to be corrected for in the extrapolation.
Below it is described how this can be done, followed by an explanation how the sieving
experiments were executed and evaluated for composites of 768, 1024, and 1536 bits. The
2048-bit case is separately described in its own section.
6

3.1

Duplicates and weight

For a multiset of relations the weight of a relation (occurring in this multiset) is defined as1
where n is the multiplicity of the relation in the multiset of relations upon completionnof the sieving step. Hence the number of unique relations is the sum of the weights of therelations in the multiset. Given the parameters of the sieving step it is relatively easy tocompute the weight of a relation that was obtained in the sieving step. This is done byinspecting the factorizations of the polynomial values and identifying the primes p in thesefactorizations for which the relation could have been obtained by lattice sieving with p as
the special q. For each such prime one checks whether lattice sieving would produce therelation (either by a conceptually simple but costly execution of the lattice sieve for thatspecial q or by a more elaborate but faster check of each step in the lattice sieve, e.g.,checking whether the cofactoring step would decompose the corresponding cofactor etc.).
Therefore, once a sufficiently uniformly distributed fraction of the sieving step has been
executed, the number of unique relations for the complete sieving step can be approximatedin an efficient manner. The procedure has been tested on several data sets where a complete
sieving step was carried out; the predicted results usually deviated by less than 1%.

3.2

Sieving experiments

For a single 768-bit, 1024-bit and 1536-bit integer the sieving experiments were conducted
as follows. Apart from the integer, a fixed polynomial pair and a smoothness bound L(chosen as described below), the input of an experiment consists of a set of parameters(B1 , B2 , A, r, C1,max , C2,max , qmax , l, nq ). The first two parameters are the factor base bounds
for the two sides, as described in the previous section, and chosen as indicated below. The
size of the sieving region per special q is set to A. As set forth in the previous section, theparameter r, an indication for the number of seconds to be spent per relation, is used tofind optimal factoring method sequences for cofactoring, and the parameters C1,max andC2,max determine up to which bit-lengths sequences are sought. The largest 2c1 for which a
non-empty sequence exists for bit-lengths (c1 , c2 ) is called C1 and analogously for C2 (thusCi ≤ Ci,max for i = 1, 2). With `i = B1 + il and ui = `i+1 − 1, for all i ∈ Z≥0 such that`i < qmax sieving is done in the length l interval [`i , ui ] for nq special q-values starting at`i +ui.
2
Given the effort involved of even doing a representative fraction of the sieving step, justa single parameter optimization is carried out per bit-length. Because after decades offactorization experiments we have never observed substantial deviations from the growthrate as expected based on the heuristic asymptotic running time, we are confident thatthe running time figures reported here are of the correct order of magnitude for relevant
composites of comparable sizes.
73.3

Evaluation

The data collected during the sieving experiment is evaluated in the following manner. For
each interval [`i , ui ] the weight of the discovered relations is computed. Then the numberof special q-values in [`i , ui ] is estimated using the prime number theorem, and the weighti)as well as the sieving time are scaled by π(ui )−π(`. The sums of the weights and the sievingnqtimes over all intervals give approximations of the expected number of unique relations andthe expected total sieving time. If the estimated number of unique relations is greater than
the number of prime ideals, the evaluation is repeated with fewer intervals, i.e., a smaller
qmax -value: due to the smaller range of special q-values the weights have to be recomputed.
The number of intervals is decreased as long as the estimated number of unique relations is
at least 2π(L). With n the final estimated number of unique relations, the combined totalnlength of all intervals and the total sieving time in core years are scaled by the factor 2π(L)(which will be close to 1) resulting in the values that are below referred to as qlen and T .

4Parameters and results of the sieving experiments

As in the previous report, the target numbers RSA768, RSA1024, RSA1536, and RSA2048
were taken from the list of RSA challenge numbers [13].

4.1

Sieving experiments for the 768-bit integer RSA768

For the experiments the polynomial pair from the actual factorization (dating back to 2009)
was used, with smoothness bound L = 237 (the value originally planned to be used to thefactorization and for which the cofactoring step was optimized, even though the larger
value 240 was used because it was deemed to be somewhat advantageous). It is considered
unlikely that these choices are far from optimal.
Many experiments with varying memory requirements were conducted to assess their effecton the running time of the sieving step. The memory requirements of the lattice siever areapproximately proportional to the size of the total factor base which can be proportionallyapproximated by π(B1 ) + π(B2 ), which in turn is roughly proportionally approximated by
B1 + B2 . Thus for several values of the sum B1 + B2 , distanced by a factor of roughly two,sieving experiments were carried out for several values of B1 , A and r, varying the latterin a reasonable region in order to find a nearly optimal set of parameters for each sum
B1 + B2 considered. The best parameters and the results are listed in the table below, withthe bold row indicating the parameter choices resulting in the lowest estimated running
time (reported in the table in core years).
8

B1
B2
1.4e9 600e6
900e6 100e6
400e6 100e6
180e6 20e6
90e6 10e6
40e6 10e6
14e6
6e6

A
232
232
231
231
230
230
230

r
2
2
2
1
2
1
2

C1
2141
2141
2141
2139
2160
2160
2160

C2
2141
2160
2160
2160
2160
2160
2160

qlen
2.99e93.49e97.86e916.8e932.5e969.2e976.3e9T
572.57561.99645.01
924.191237.482066.412737.34

Most of the time 24 sieving experiments were carried out simultaneously on the 24 coresof the machine used for the experiments.
Since RSA768 has already been factored, a comparison is in order. This is not entirely
straightforward due to a number of unavoidable differences: the original computation was
carried out on a wide variety of machines with differing memory sizes so that several setsof parameters had to be used; the smoothness bound was larger, namely 240 ; and moresieving was done to somewhat alleviate the subsequent parts of the computation. However,limiting the comparison to the parameter set for the largest memory machines while scaling
for the clock rates, and taking into account the oversieving, the figures are reasonably close.
4.2

Sieving experiments for the 1024-bit integer RSA1024

For this integer a modest effort was spent on choosing a polynomial pair and the smoothness
bound was set to L = 242 (compared to 237 for 768-bit a growth by approximately the squareroot of the anticipated running time increase; see also below right after the table).
The experiments were carried out as for the 768-bit case, resulting in the table below
where the best parameters are listed for each considered sum B1 + B2 , and with the lowest
estimated running time in bold. Unlike the 768-bit case each sieving experiment used all
24 cores: for the larger factor base sizes – and thus memory requirements – there was no
choice; for the smaller factor base sizes reducing the number of cores per sieving experiment
would have been an option, but for the sake of comparison we chose not to do so.
B1
B2
62e9
2e9
30e9 2e9
14e9
2e9
7e9
1e9
3.5e9 500e6
1.8e9 200e6
900e6 100e6
450e6 50e6
225e6 25e6
110e5 18e6

A
237
237
237
235
234
235
235
235
235
236

r
200
200
200
200
200
200
200
200
200
200

C1
2200
2199
2199
2199
2226
2227
2228
2229
2244
2249
9

C2
2192
2192
2192
2192
2192
2192
2192
2192
2192
2192

qlen
T
131e9 1.68e6
139e9 1.52e6
159e9 1.57e6
718e9 1.77e6
1.6e12 2.26e6
1.09e12 2.57e6
1.44e12 3.17e6
2.08e12 4.28e6
3.05e12 6.9e6
2.5e12 12.6e6

As for the 768-bit case, the parameters reported in the above table for the 1024-bit case are
not affected by suboptimal hardware restrictions and thus optimal (given values of the sum
B1 + B2 ), with the relatively small exception (compared to hardware-caused suboptimal
choices encountered for larger bit-lengths, cf. below) that the former case could be done
single-threaded, whereas for the present one multi-threading had to be used. This makes
it possible and worthwhile to compare the present 1024-bit results to an extrapolation of
the earlier 768-bit case. As usual the extrapolation is done by setting to 0 the o(1)-term in1024
the definition of theqfunction
and N = 2768
q LN [α, c] and calculating the ratio for N = 2. This leads to ratios of 35 for the B1 and B2 -values and of
for α = 13 and c = 3 89 or 3 64
91221 for the size of the total sieving region (i.e., A times the number of special q) and forthe running time.

At first glance the experiments and the extrapolation seem to match quite well regarding
the factor base bounds with ratios of 32 versus 35. However, the rows above and below the
optimal ones suggest that the optimal B1 + B2 in the 768-bit case is slightly above 1e9 andin the 1024-bit case slightly below 32e9. Nevertheless, the deviation seems to be less thana factor of 2. Regarding the total sieving area the ratio obtained from the experiments
is about 1100 which is very close to the extrapolation. Only with respect to the running
time the experiment is off by a factor of 2.2, taking more than twice the time suggestedby the extrapolation. Comparing in more detail the sieving runs reveals two issues that
explain this effect. Firstly, in the 1024-bit case sieving tasks used 24 threads whereas they
were single-threaded in the 768-bit case; one might expect that a similar run on a one coremachine would reduce the factor of 2.2 to less than 2. Secondly, B1 and B2 are below 232
in the 768-bit case, making it possible to use faster code and less memory.

4.3

Sieving experiments for the 1536-bit integer RSA1536

For this integer the polynomial pair and smoothness bound L = 250 were taken from theprevious report.
Extrapolating (as described above) the 1024-bit factor base bounds suggests that for the1536-bit case the optimal value for B1 + B2 would be in the range between 5e12 and 20e12,
thus requiring several tens of terabytes of memory. The 256GB of memory available on
the machine to be used imposes a largest possible (and suboptimal) value of 114e9 forB1 + B2 , so only that value was used, with lower ones even worse and thus not considered.
Moreover, since sieving for a single special q over a region of size A = 245 takes more thana day on the 24-core machine, the parameters B1 , A and r were not selected by extensive
experiments but as follows. For several values of B1 and r, lattice sieving for one special q
was done for a relatively small value of A such as 237 or 238 , and the expected number ofrelations (cf. previous report or 2048-bit case below) was used to choose the best values for
B1 and r. These values were fixed and A was increased until the expected maximal special
q would be well below L.
10

This procedure led to the following parameters and results (with, as usual, r in seconds
and T in core years).
B1
110e9

B2
4e9

A
245

r
C1
200000 2320

C2
2240

qlen
T
277e12 0.94e12

With the exception of the polynomial selection the data in the 1024-bit case are on relatively
solid ground so that one might try to extrapolate it to the 1536-bit case. A computation
as in the 1024-bit case gives a ratio of about 300 for the factor base bounds and a ratio
of about 105 both for the size of the total sieving region and for the running time. Since
the extrapolated factor base bounds are a hundred times bigger than those used in theexperiment one might expect a considerable improvement by using bounds in the region
that would follow from the extrapolation. Unfortunately, such experiments would requirea machine with a main memory on the order of about 25TB which was not at our disposal.
However, one might use the data for varying factor base bounds in the 768- and 1024-bit
cases for the following speculative extrapolation. Namely, in these cases comparing the1of it, one gets a ratio near 5 bothdata for the best value of B1 + B2 to a value near 100
for the size of the total sieving region and for the running time. Thus if B1 = 11e12,
B2 = 400e9 would be used for the 1536-bit case it is reasonable to predict that both thetotal sieving region and the running time are about 5 times smaller than the figures forthe actual experiment reported in the above table. This would fit the extrapolation using
LN [α, c] quite well.
4.4

Sieving experiments for the 2048-bit integer RSA2048

Again, for this integer the polynomial pair and smoothness bound L = 257 were taken fromthe previous report.
As in the 1536-bit case the only meaningful choice for the factor base bounds is to choose
them as large as possible while fitting into the available memory. It follows that the same
factor base bounds were chosen as in the 1536-bit case. Choosing the other parameters
revealed an obstacle, namely that a similar approach as in the 1536-bit case would leadto a sieving region size A far above 250 , perhaps even above 255 . Thus sieving for a single
special q would take months or even years. Therefore an approach similar to the one in theprevious report was used. More precisely, the special q was chosen as q = q1 q2 with qi ∈ Qi
where Q1 is the set of special q in the interval [110e9, 300e9] and Q2 is the set of special q
in the interval [300e9, 625e9].
Another obstacle was that it takes on average several core years to produce one relation,
so that modest computing resources would by far not allow to obtain sufficiently many
relations for an estimate of the total number of relations and the number of duplicates.
Therefore the number of relations was estimated by analyzing the smoothness probabilities of the cofactors (cf. previous report; essentially for each pair of bit-lengths (c1 , c2 ) a
11

probability was precalculated that the cofactoring strategy associated to these bit-lengths
would report both cofactors being L-smooth, and these probabilities are summed for all
pairs of cofactors).
The procedure for estimating the percentage of duplicates described in the previous report
was also applied here. Essentially, approximations for the number of relations nrel andfor the number of duplicates ndup were calculated. Several simplifications were used whichn. For the choice of the range
heuristically rather increase than decrease the quotient ndup
reland shape of special q as above the formulae of the previous report become

 

X X
log g1 (q1 q2 A) − log q1 q2
log g2 (q1 q2 A)
nrel =
Aρ
ρ
log
L
log L
q ∈Q q ∈Q
1

1

2

2

and


log g1 (q1 min(q2 , r2 )A) − log q1 q2 r2
1 X X XA
ρ×ndup =
2 q ∈Q q ∈Q r ∈Q max(q2 , r2 )
log L
1
1 2
2 2
2


log g2 (q1 min(q2 , r2 )A)
×ρ
log L


1 X X Xlog g1 (min(q1 , r1 )q2 A) − log q1 r1 q2A+ρ
×2 q ∈Q r ∈Q q ∈Q max(q1 , r1 )
log L
1
1 1
1 2
2


log g2 (min(q1 , r1 )q2 A)
×ρ
,
log L
where g1 and g2 are functions approximating the polynomial values, as defined in theprevious report.
Using the choices and tools above the parameters and results are as follows.
B1
110e9

B2
4e9

A
239

r
800e6

C1
2390

C2
2280

T
128e15In this case most extrapolations would be mere speculation. As in the 1536-bit case one
might expect to reduce the running time by increasing the factor base bounds considerably.
This would also imply that one can use prime special q which would facilitate comparisons
to the smaller cases.

12References
1. D. V. Bailey, B. Baldwin, L. Batina, D. J. Bernstein, P. Birkner, J. W. Bos, G. van Damme, G. de Meulenaer,
J. Fan, T. Güneysu, F. Gurkaynak, T. Kleinjung, T. Lange, N. Mentens, C. Paar, F. Regazzoni, P. Schwabe,and L. Uhsadel. The Certicom challenges ECC2-X. Special-purpose Hardware for Attacking Cryptographic
Systems – SHARCS 2009, 2009. http://www.hyperelliptic.org/tanja/SHARCS/record2.pdf.
2. J. W. Bos, M. E. Kaihara, T. Kleinjung, A. K. Lenstra, and P. L. Montgomery. On the security of 1024bit RSA and 160-bit elliptic curve cryptography. Cryptology ePrint Archive, Report 2009/389, 2009. http://eprint.iacr.org/.
3. G. Kalai. How quantum computers can fail. http://arxiv.org/abs/quant-ph/0607021v3, 2008.
4. G. Kalai. The quantum computer puzzle. http://www.ams.org/journals/notices/201605/rnoti-p508.pdf,
2016.
5. T. Kleinjung. Evaluation of complexity of mathematical algorithms. http://www.cryptrec.go.jp/exreport/
cryptrec-ex-0601-2006.pdf, 2006.
6. T. Kleinjung. Polynomial selection, presented at the CADO workshop. See http://cado.gforge.inria.fr/
workshop/slides/kleinjung.pdf, 2008.
7. T. Kleinjung. Quadratic sieving. Mathematics of Computation, 85:1861–1873, 2016.
8. T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé, J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery,D. A. Osvik, H. te Riele, A. Timofeev, and P. Zimmermann. Factorization of a 768-bit RSA modulus. In
T. Rabin, editor, Crypto 2010, volume 6223 of Lecture Notes in Computer Science, pages 333–350. Springer,
Heidelberg, 2010.
9. A. K. Lenstra. Unbelievable security: Matching AES security using public key systems. In C. Boyd, editor,
ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer Science, pages 67–86. Springer, Heidelberg,
2001.
10. A. K. Lenstra and H. W. Lenstra Jr. The Development of the Number Field Sieve, volume 1554 of Lecture
Notes in Mathematics. Springer-Verlag, 1993.
11. A. K. Lenstra and E. R. Verheul. Selecting cryptographic key sizes. Journal of Cryptology, 14(4):255–293,
2001.
12. A. Miele, J. W. Bos, T. Kleinjung, and A. K. Lenstra. Cofactorization on graphics processing units. In
L. Batina and M. Robshaw, editors, Cryptographic Hardware and Embedded Systems – CHES 2014, volume
8731 of Lecture Notes in Computer Science, pages 335–352. Springer, 2014.
13. RSA the security division of EMC. The RSA challenge numbers. Formerly on http://www.rsa.com/rsalabs/
node.asp?id=2093, now on http://en.wikipedia.org/wiki/RSA_numbers.
14. A. Shamir and E. Tromer. Factoring large number with the TWIRL device. In D. Boneh, editor, Crypto 2003,
volume 2729 of Lecture Notes in Computer Science, pages 1–26. Springer, Heidelberg, 2003.
15. P. Zimmermann. Integer factoring records. https://members.loria.fr/PZimmermann/records/factor.html,
2013.
16. P. Zimmermann. Previous records. https://members.loria.fr/PZimmermann/records/factor-previous.
html#general, 2013.

13

5

Appendix A: Polynomial pairs

The polynomial pairs used in the experiments are listed below.
RSA-768:
This is the polynomial pair used in the actual factorization from 2009.

f1 = 265482057982680x6+1276509360768321888x5−5006815697800138351796828x4−46477854471727854271772677450x3+6525437261935989397109667371894785x2−18185779352088594356726018862434803054x−277565266791543881995216199713801103343120

f2 = 34661003550492501851445829x−1291187456580021223163547791574810881
RSA-1024:

f1 = 1000000001873592720x6−7446449158492361441646604532x5−2855448129341973849097555875554322x4−10382665418989066951927608603558864515815x3+11602682022152240220800022686402091317734574987x2+5577186790441970080185754971249399812968739265217915x+552709389072807088966981033461796318746449416206836556375

f2 = 50793101154086383x−2265120061143968874534624738373239732665962281812
RSA-1536:
This is the same polynomial pair as in the previous report.
14

f1 = 1000000000000000037811142945142568000x7−43714365350271595218854107295531451599556144x6+30328754671516292832035468235744202558674475901616x5−2549632694806349159734389882357104975174959388666079090x4−7434766214490707054261180439521079108132968739472265699676x3+26941031676370465249694738904702978153213780731967578381868353x2+45868218740012733930559584256165992747756385156566775760747640786x−48867794882451008441424264335735273573088241264624142804371580106080

f2 = 205334469089201645309341276310576122905417473x−7856571290567634945150691614513931635402668625054838502550321
RSA-2048:
This is the same polynomial pair as in the previous report (there is a typo in the previous
report resulting in the omission of the last two digits of the x2 -coefficient of f1 ).

f1 = 100000000000000000000000000000000000073338147424598156000x7+8395882633588606238472583967532001708930835342294610074799259311x6−1624323846587182617948662934734932766459757587817030957853256978619586x5−1629792266744980170101888726089171334493378868821693528092987281939755424x4+33842219052921654312275628323473891052030445427581764495124943311088430533903x3+9716912639751006582769498331827822475017336741488801452569420246914089266896807x2−127658905721988738113694551290560677881909461129950694195199704883206539032920354252x+70780743244066711466692928940077321828000766324763392134444939614936295115875125481344

f2 = 41123412601722865693107152959526055267629x−114112405465044179083292898071688380999575821246316812608380320780980683979836071

15

6

Appendix B: Technical data of the PC

Below are listed some technical data of the PCs used for the sieving experiments.
CPU
2× Intel Xeon E5-2680 v3 (Haswell)
Cores (per CPU)
12
Clock rate
2.5 GHz
Cache size (per CPU) L2: 12 × 256 kB, L3: 30 MB
Memory16 × 16 GB DDR4-2133

16