Reference / Paper · 2020
Comparing the Difficulty of Factorization and Discrete Logarithm: a 240-digit Experiment (CRYPTO 2020)
RSA-240, DLP-240 and RSA-250 computed with the number field sieve.
Reference / Paper · 2020
RSA-240, DLP-240 and RSA-250 computed with the number field sieve.
Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment⋆ arXiv:2006.06197v1 [cs.CR] 11 Jun 2020 Fabrice Boudot1 , Pierrick Gaudry2 , Aurore Guillevic2 , Nadia Heninger3 , Emmanuel Thomé2 , and Paul Zimmermann2 1 2 Université de Limoges, XLIM, UMR 7252, F-87000 Limoges, France Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France 3 University of California, San Diego, USA In memory of Peter L. Montgomery Abstract. We report on two new records: the factorization of RSA-240, a 795-bit number, and a discrete logarithm computation over a 795-bit prime field. Previous records were the factorization of RSA-768 in 2009 and a 768-bit discrete logarithm computation in 2016. Our two computations at the 795-bit level were done using the same hardware and software, and show that computing a discrete logarithm is not much harder than a factorization of the same size. Moreover, thanks to algorithmic variants and well-chosen parameters, our computations were significantly less expensive than anticipated based on previous records. The last page of this paper also reports on the factorization of RSA-250. 1 Introduction The Diffie-Hellman protocol over finite fields and the RSA cryptosystem were the first practical building blocks of public-key cryptography. Since then, several other cryptographic primitives have entered the landscape, and a significant amount of research has been put into the development, standardization, cryptanalysis, and optimization of implementations for a large number of cryptographic primitives. Yet the prevalence of RSA and finite field Diffie-Hellman is still a fact: between November 11, 2019 and December 11, 2019, the ICSI Certificate Notary [21] observed that 90% of the TLS certificates used RSA signatures, and 7% of the TLS connections used RSA for key exchange. This holds despite the much longer key sizes required by these primitives compared to elliptic curves: based on the asymptotic formulas for the best known cryptanalysis algorithms, the required key size for RSA or finite field Diffie-Hellman is roughly estimated to grow as a cubic function of the security parameter, while the required key size for elliptic curve cryptosystems grows only as a linear function of the security parameter.4 c IACR 2020. This article is the final version submitted by the authors to the IACR and to Springer-Verlag on 2020-06-09 for CRYPTO2020, available on ePrint at https://eprint.iacr.org/2020/xxxx. The version published by Springer-Verlag will be available in August 2020. 4 A security parameter ǫ asserts that cryptanalysis requires 2ǫ operations; assuming Moore’s law, the security parameter could be seen as growing linearly with time. ⋆ Over the last few years, the threat posed by quantum computers has been used as a justification to postpone the impending replacement of RSA and finite field Diffie-Hellman by alternatives such as elliptic curve cryptography [33], resulting in implementation choices that seem paradoxical from the perspective of classical cryptanalysis. Key sizes for RSA and finite field Diffie-Hellman have become unwieldy. To meet a 128-bit security strength, it is widely accepted that both schemes require a key size of approximately 3072 bits (see e.g., the 2018 ECRYPT-CS Recommendations). While it is easy to deal with such key sizes in environments where computing power is plentiful (laptop and desktop computers, or cell phones), a surprising amount of public key cryptography in use employs weak key strengths. There are two main factors contributing to the use of weak key sizes in practice. First, implementations may use weak key sizes to ensure backward compatibility. For example, a crucial component in the FREAK and Logjam attacks was the widespread support for weakened “export-grade” cipher suites using 512-bit keys [1]; the Java JDK versions 5-8 originally supported Diffie-Hellman and DSA primes of at most 1024 bits by default. Second, in embedded environments, or when very little computational power is allotted to public-key cryptographic operations, small key sizes are not rare. As an example, in 2018, an off-the-shelf managed network switch purchased by the authors shipped with a default RSA ssh host key of 768 bits (despite a $2,000 USD list price), a key size that has been broken since 2009 in the academic world. The main goal of this article is to assess the difficulty of the mathematical problems that underpin the security of RSA and finite field Diffie-Hellman and DSA, namely integer factorization (IF) and discrete logarithm (DL). We are interested both in the feasibility of cryptanalysis of these problems as well as in their relative difficulty. Our targets are RSA-240, from the RSA Factoring Challenge, and DLP-240, denoting the challenge of computing discrete logarithms modulo p = RSA-240 + 49204, which is the smallest safe prime above RSA-240 (i.e., (p − 1)/2 is also prime). Both previous records were 768-bit keys, with results dating back to 2009 [27] and 2016 [29]. The total cost of our computation is about 1000 core-years for RSA-240, and 3200 core-years for DLP-240. Here and throughout this article, the core-years we mention are relative to the computing platform that we used most, namely Intel Xeon Gold 6130 CPUs with 16 physical cores (32 hyperthreaded cores) running at 2.10GHz. A core-year is the use of one of these physical cores for a duration of one year. As in the previous records, our computations used the Number Field Sieve algorithm (NFS for short), which has variants both for integer factoring and finite field discrete logarithms. Improvements in cryptanalysis records are to be expected. In this article, our contribution is not limited to reaching new milestones (and reminding people to get rid of outdated keys). Rather, it is interesting to report on how we reached them: – We developed a testing framework that enabled us to precisely select, among a wide variety with complex interactions, parameters that influence the run2 ning time of NFS. We were able to accurately predict important measures such as the matrix size. – Some folklore ideas that have been known for some time in the NFS community played a very important role in our computation. In particular the composite special-q used in relation collection for DLP-240 proved extremely beneficial, and so did batch smoothness detection, which we used both for RSA-240 and DLP-240. This is the first time that this latter technique has been used in a factoring record for general numbers (it was used in [28], in a very specific context). These techniques, together with our careful parameter selection, contributed to a significantly faster computation than extrapolation from the running times of previous records would have suggested. Even on similar hardware, our relation collection effort for the 795-bit DLP computation took 25% less time than the reported relation collection effort of the previous 768-bit DLP record. – Furthermore, we computed two records of the same size, RSA-240 and DLP240, at the same time and using hardware of the same generation. This is completely new and gives a crucial data point for the assessment of the relative difficulty of IF and DL. While it is commonly believed that DL is much harder than IF, we show that the hardness ratio is roughly a factor of 3 for the current 800-bit range for safe primes, much less than previously thought. – Last but not least, our computations were performed with the open-source software Cado-NFS [36]. Reproducing our results is possible: we have set up a companion code repository at https://gitlab.inria.fr/cado-nfs/records that holds the required information to reproduce them. We complement the present work with another record computation, the factoring of RSA-250, for which we used parameters similar to RSA-240. Details for this additional record are given at the end of the paper. This article is organized as follows. We give a brief introduction to key aspects of NFS in Section 2. In Sections 3 to 7 we detail the main steps of NFS, how we chose parameters, and how our computations proceeded, both for factoring and discrete logarithm. Section 8 gives further details on the simulation mechanism that we used in order to predict the running time. Section 9 concludes with a comparison with recent computational records, and a discussion on the relative hardness of the discrete logarithm and factoring problems. 2 Background on the Number Field Sieve The Number Field Sieve (NFS) is an algorithmic framework that can tackle either of the two following problems: – Integer factorization (IF): given a composite integer N , find a non-trivial factorization of N . 3 – Discrete logarithm in finite fields (DL): given a prime-order finite field5 Fp and a subgroup G of prime order ℓ within F∗p , compute a non-trivial homomorphism from G to Z/ℓZ. By combining information of this kind for various ℓ, given g, y ∈ F∗p , one can compute x such that g x = y. When the need arises, the algorithms for the two problems above are denoted NFS and NFS-DL, respectively. Most often the acronym NFS is used for both cases. Furthermore, in the few cases in this paper where we work with the prime factors of N , we call them p and q. Of course, p here shall not be confused with the prime p of the DLP case. The context allows to avoid the confusion. NFS is described in the book [30]. So-called “special” variants of NFS exist as well, and were historically the first to be developed. These variants apply when the number N or p has a particular form. Large computations in these special cases were reported in [2,17,28]. In this work, we are concerned only with the general case (GNFS). The time and space complexity can be expressed as LN (1/3, (64/9)1/3)1+o(1) = exp (64/9)1/3 (log N )1/3 (log log N )2/3 (1 + o(1)) for factoring. For discrete logarithms in a subgroup of F∗p , N is substituted by p in the above formula. In both cases, the presence of (1 + o(1)) in the exponent reveals a significant lack of accuracy in this complexity estimate, which easily swallows any speedup or slowdown that would be polynomial in log N . polynomial selection sieving filtering linear algebra square root p, q N NFS for factoring: given an RSA modulus N , find p, q such that N = pq. polynomial selection sieving filtering linear algebra p y, g log db one-off precomputation descent x per-key computation x NFS for DLP: given g ≡ y mod p, find x. Fig. 1. Main steps of NFS and NFS-DL. The Number Field Sieve is made up of several independent steps, which are depicted in Figure 1. The first step of NFS, called polynomial selection, 5 Variants for non-prime finite fields also exist, but are not covered here. 4 determines a mathematical setup that is well suited to dealing with the input N (or p). That is, we are searching for two irreducible polynomials f0 and f1 in Z[x] that define two algebraic number fields K0 = Q(α0 ) and K1 = Q(α1 ) (with fi (αi ) = 0), subject to some compatibility condition. The resulting maps are depicted in the diagram in Figure 2. x 7→ α0 Z[x] x 7→ α1 Z[α0 ] Z[α1 ] ψ0 : α0 7→ m ψ1 : α1 7→ m Z/pZ or Z/N Z Fig. 2. The mathematical setup of NFS. To be compatible, f0 and f1 should have a common root m modulo p (or, likewise, modulo N ), used in the maps ψ0 and ψ1 in Figure 2. This condition is difficult to ensure modulo a composite integer N , and most efficient constructions are limited to choosing f0 as a linear polynomial, so that Z[α0 ] is a subring of Q. This leads to commonly used terminology that distinguishes between the “rational side” (f0 ) and the “algebraic side” (f1 ). When dealing with IF-related considerations, we also use this terminology. In contrast, for NFS-DL, other constructions exist that take advantage of the ability to find roots modulo p. Based on the mathematical setup above, the most time-consuming phase of NFS consists of collecting relations. We search for elements a − bx ∈ Z[x], preferably with small coefficients, such that the two integers6 Res(a − bx, f0 ) and Res(a − bx, f1 ) are smooth, i.e., factor into small prime numbers below some chosen large prime bound. This ensures that the ideals (a − bα0 )OK0 and (a − bα1 )OK1 both factor into ideals within finite sets called F0 and F1 .7 The main mathematical obstacle to understanding NFS is that we cannot expect a − bαi for i ∈ {0, 1} to factor into elements of Z[αi ]. Only factorization into prime ideals, within the maximal orders OKi ,Qholds. As such, even given known ideal factorizations of the form (a−bαi )Oi = p∈Fi pep,a,b , it is impossible to use the diagram in Figure 2 to write a relation of the following kind (in either Z/N Z or Z/pZ, depending on the context): Y Y ψ0 (pep,a,b ) “≡” ψ1 (pep,a,b ). (1) p∈F0 p∈F1 6 A common abuse of terminology is to use the term “norm” to denote Res(a − bx, fi ), while in fact the latter coincides with the norm of a − bαi only when fi is monic. 7 The terms smoothness bound and factor base are fairly standard, but lead to ambiguous interpretations as we dive into the technical details of how relation collection is performed. Both are therefore avoided here, on purpose. 5 Indeed the maps ψi are defined on elements, not ideals. A prime ideal, or a factorization into prime ideals, does not uniquely identify an element of Ki , because of obstructions related to the unit group and the class group of the number field Ki . To make an equality similar to (1) work, additional data is needed, called quadratic characters in the context of factoring [10, §6] and Schirokauer maps in the discrete logarithm context [35]. With this additional information, relations that are functionally equivalent to Equation (1) can be obtained. The general goal of NFS, once relations have been collected, is: – in the IF context, to combine (multiply) many relations together so as to form an equality of squares in Z/N Z. To achieve this goal, it suffices to only keep track of the valuations ep,a,b modulo 2. The right combination can be obtained by searching for a left nullspace element of a binary matrix; – in the DL context, to view the multiplicative relations as additive relations involving unknown logarithms of the elements in F0 and F1 , and to solve the corresponding linear system for these unknowns. These logarithms, and the linear system, are defined modulo ℓ, which is the order of the subgroup of F∗p that we are working in. (If the system were homogeneous, solving it would require a right nullspace element of a matrix defined modulo ℓ.) In both cases (factoring and discrete logarithm), we need a linear algebra calculation. The matrix rows are vectors of valuations, which are by construction very sparse. Note however that record-size computations with NFS typically collect billions of relations, which is a rather awkward data set to deal with. The linear algebra step therefore begins with a preprocessing step called filtering, which carries out some preliminary steps of Gaussian elimination with the aim of reducing the matrix size significantly while keeping it relatively sparse. The linear algebra step that follows is the second most expensive computational step of NFS. Once the solution to the linear algebra problem has been found, the final task is to factor N given an equality of squares modulo N , or to compute arbitrary discrete logarithms based on a database of known logarithms derived from the solution of the linear system. This final result is obtained via some additional steps which, while nontrivial, are computationally insignificant compared to the rest of the computation. NFS can be implemented in software. Our computation was carried out exclusively with the Cado-NFS implementation [36]. In Sections 3 to 7, we examine the underlying algorithms as well as the computational specifics of the different steps of NFS. 3 Polynomial selection Polynomial selection can be done using a variety of algorithms, both in the factoring context [25,26,32,3] or in the discrete logarithm context, which allows additional constructions such as [22]. Not all choices of polynomials (f0 , f1 ) that permit the structure in the diagram in Figure 2 perform equally well. Hence, it 6 is useful to try many different pairs (f0 , f1 ) until a good one is found. The main optimization criteria are meant to ensure that on the one hand Res(a − bx, f0 ) and Res(a − bx, f1 ) are somewhat small, and on the other hand they are likely to have many small prime factors. As detailed in [25], the most important task in polynomial selection is to quickly discard the less promising pairs, and efficiently rank the promising ones with a sequence of estimators, from coarse-grained estimators to finer-grained ones. Finally, a small-scale sieving test can be run in order to select the polynomial pair to use for the rest of the computation among the final set of candidates. We followed exactly this approach, using the Murphy-E value from [32] as well as the modified estimator E ′ suggested in [14] as estimators. We performed sample sieving for a few dozen of the best candidates. Cado-NFS can do this easily with the random-sample option. 3.1 Computational data RSA-240. We used Kleinjung’s algorithm [25,26], with improvements from [3], and searched for a polynomial pair with deg f0 = 1 and deg f1 = 6. We forced the leading coefficient f1,6 of f1 to be divisible by 110880, to ensure higher divisibility by 2, 3, 5, 7, 11. The parameter P used (see [26]) was P = 2 · 107 and we searched up to f1,6 = 2 · 1012 . The cost of the search was about 76 core-years. It was distributed over many computer clusters, and took only 12 days of calendar time. We kept 40 polynomial pairs: the top 20 with the best Murphy-E values, and the top 20 with the modified E ′ value [14]. After some sample sieving, two clear winners emerged, and distinguishing between both was actually quite hard. In the end we chose the one optimized for the classical Murphy-E value, with |Res(f0 , f1 )| = 120N : f1 = 10853204947200 x6 − 221175588842299117590564542609977016567191860 − 4763683724115259920 x5 + 1595712553369335430496125795083146688523 x − 6381744461279867941961670 x4 + 179200573533665721310210640738061170 x2 + 974448934853864807690675067037 x3 f0 = 17780390513045005995253 x − 105487753732969860223795041295860517380 For each polynomial fi (x), we denote by Fi (x, y) = y deg fi fi (x/y) the corresponding homogeneous bivariate polynomial. DLP-240. As in [29], we used the Joux-Lercier selection algorithm [22], searching for a pair (f0 , f1 ) with f1 of degree d with small coefficients, and f0 of degree d − 1 with coefficients of order p1/d . As in [29], we used d = 4 which is optimal for this size, with coefficients of f1 bounded by 150 in absolute value, compared to 165 in [29]. The cost of the search was about 152 core-years, and only about 18 days of calendar time. We kept the 100 best pairs according to their Murphy-E value, and chose the winning polynomial pair based on the results of sample sieving. 7 As in the RSA-240 case, the very best handful of polynomials provided almost identical yields. We ended up using the following pair, with |Res(f0 , f1 )| = 540p: f1 = 39x4 + 126x3 + x2 + 62x + 120 f0 = 286512172700675411986966846394359924874576536408786368056x3 + 24908820300715766136475115982439735516581888603817255539890x2 − 18763697560013016564403953928327121035580409459944854652737x − 236610408827000256250190838220824122997878994595785432202599 Note that although there is a clear correlation between the efficiency of a polynomial pair and its Murphy-E value, the ranking is definitely not perfect [14]; in particular, the top scoring polynomial pair according to Murphy-E finds 10% fewer relations than the above one. 4 Relation collection The relation collection uses a technique called lattice sieving [34]. Lattice sieving borrows from the terminology of special-q sieving [15]. We call special-q ideals a large set of ideals of one of the two number fields8 . For each such special-q, the search for relations is done among the pairs (a, b) such that the prime ideals dividing q appear in the factorization9 of (a − bα0 )OK0 (or (a − bα1 )OK1 ). These (a, b) pairs form a lattice Lq in Z2 , which depends on q. Let (u, v) be a Gaussreduced basis of Lq . To enumerate small points in Lq , we consider small linear combinations of the form (a, b) = iu + jv. In order to search for good pairs (a, b) in Lq , we use the change of basis given by (u, v), and instead search for good pairs (i, j) such that both Res(a − bx, f0 ) and Res(a − bx, f1 ) are smooth. The set of explored pairs (i, j) is called the sieve area, which we commonly denote by A. For performance it is best to have A of the form [−I/2, I/2) × [0, J) for some integers I and J, and I a power of two. This implies that as we consider multiple special-qs, the sieved rectangles drawn in Figure 3(a) (whose intersections with Z2 most often have very few common points, since divisibility conditions are distinct) lead us to implicitly consider (a, b) pairs that generally have small norm, but are not constrained to some area that has been defined a priori. In fact, various strategies can be used to make small adjustments to the sieve area depending on q in order to limit the spread of the zones reached in Figure 3(a). Relation collection finds pairs (a, b) (or, equivalently, pairs (i, j)) such that two smoothness conditions hold simultaneously (see §2). We thus have two sides It is possible to mix special-q ideals from both number fields, as done in [17], or even hybrid special-q involving contributions from both sides. 9 By factorization, we implicitly mean “numerator of the factorization”. Furthermore we factor ideals such as (a − bα)OK , yet the maximal order OK is generally too expensive to compute. It turns out that if Res(a−bx, f ) is smooth and fully factored, then it is easy to do. How to deal with these technicalities is well known, and not discussed here (see [12, chapters 4 and 6]). 8 8 (a) (b) (c) Fig. 3. (a): Examples of (i, j) rectangles for various lattices Lq within the (a, b) plane. (b): Sieving for a prime p in the (i, j) rectangle. (c): Sieved locations can be quite far apart, and accessing them naively can incur a significant memory access penalty. to consider. In the description below, we use F to denote either F0 or F1 , as the same processing can be applied to both sides. Likewise, we use f and α to denote either f0 and α0 , or f1 and α1 . One of the efficient ways to find the good pairs (i, j) is to use a sieving procedure. Let p be a moderate-size prime ideal in F , subject to limits on |Norm p| that will be detailed later. Identify the locations (i, j) such that p | (a − bα). These locations again form a lattice in the (i, j) coordinate space, as seen in Figures 3(b)–(c) and hence implicitly a sub-lattice of Lq . Record the corresponding contribution in an array cell indexed by (i, j). Repeat this process for many (not necessarily all) prime ideals in F , and keep the array cells whose recorded contribution is closest to the value |Res(a − bx, f )|: those are the most promising, i.e., the most likely to be smooth on the side being sieved. Proceed similarly for the other side, and check the few remaining (a, b) pairs for smoothness. Note that as p varies, the set of locations where p divides (a − bα) becomes sparser (see Figure 3(c)), and dedicated techniques must be used to avoid large memory access penalties. An alternative approach is to identify the good pairs (i, j) with product trees, using “batch smoothness detection” as explained in [6]. Among a given set of norms, determine their smooth part by computing their gcd with the product of the norms of all elements of F at once. This is efficient because it can be done while taking advantage of asymptotically fast algorithms for multiplying integers. This approach was used profitably for the previous 768-bit DLP record [29]. Among the mind-boggling number of parameters that influence the sieving procedure, the most important choices are the following. – The large prime bound that determines the set F . These bounds (one on each side) define the “quality” of the relations we are looking for. Cado-NFS uses the notation lpb for these bounds. – The q-range and the size of the sieve area #A. This controls how many special-qs we consider, and how much work is done for each. The amount of work can also vary depending on the norm of q. The ratio between the norms of the smallest and largest special-q is important to examine: a large ratio increases the likelihood that the same relations are obtained from several different special-q (called duplicates), and causes diminishing returns. Enlarging 9 the sieve area increases the yield per special-q, but also with diminishing returns for the larger area, and costs extra memory. In order to collect the expected number of relations, it is necessary to tune these parameters. – The size of the prime ideals p ∈ F being sieved for, and more generally how (and if ) these ideals are sieved. Cado-NFS uses the notation lim for this upper bound, and we refer to it as the sieving (upper) bound. As a rule of thumb, we should sieve with prime ideals that are no larger than the size of the sieve area, so that sieving actually makes sense. The inner details of the lattice sieving implementation also define how sieving is performed, e.g., how we transition between algorithms in different situations like those depicted in Figures 3(b) and 3(c), along with more subtle distinctions. This has a significant impact on the amount of memory that is necessary for sieving. When sieving is replaced by batch smoothness detection, we also use the notation lim to denote the maximum size of primes that are detected with product trees. – Which criteria are used to decide that (a, b) are “promising” after sieving, and the further processing that is applied to them. Typically, sieving identifies a smooth part of Res(a − bα, f ), and a remaining unfactored part (cofactor). Based on the cofactor size, one must decide whether it makes sense to seek its complete factorization into elements of F . In this case Cado-NFS uses the Bouvier-Imbert mixed representation [9]. Any prime ideal that appears in this “cofactorization” is called a large prime. By construction, large primes are between the sieving bound and the large prime bound. 4.1 Details of our relation search One of the key new techniques we adopt in our experiments is how we organize the relation search. The picture is quite different in the two cases. For IF, this phase is the most costly, and can therefore be optimized more or less independently of the others. On the other hand for DL, the linear algebra becomes the bottleneck by a large margin if the parameters of the relation search are chosen without considering the size of the matrix they produce. The first component that we adjust is the family of special-qs that we consider. In the DL case, a good strategy to help the filtering and have a smaller matrix is to try to limit the number of large ideals involved in each relation as much as possible. The approach taken in [29] was to have special-qs that stay small, and therefore to increase the sieve area #A, which comes at a cost. We instead chose to use composite special-qs (special-q ideals with composite norm), reviving an idea that was originally proposed in [24] in the factoring case to give estimates for factoring RSA-1024. This idea was extended in [7, Section 4.4] to the discrete logarithm case, but to our knowledge it was never used in any practical computation. We pick composite special-qs that are larger than the large prime bound, but whose prime factors are small, and do not negatively influence the filtering. Because there are many of them, this no longer requires a large sieve area, so that we can tune it according to other tradeoffs. 10 In the context of IF, we chose the special-qs more classically, some of them below lim, and some of them between lim and lpb. Another important idea is to adapt the relation search strategy depending on the type of special-q we are dealing with and on the quality of the relations that are sought. A graphical representation of these strategies is given in Figure 4. In the DL case, we want to limit as much as possible the size of the matrix and the cost of the linear algebra. To this end, we used small sieving bounds, and allowed only two large primes on each side, with rather small large prime bounds. These choices have additional advantages: a very small number of (i, j) candidates survive the sieving on the f0 -side (the side leading to the largest norms), so that following [29], we skipped sieving on the f1 -side entirely and used factorization trees to handle the survivors, thus saving time and memory by about a factor of 2 compared to sieving on both sides. In the IF case, the same idea can also be used, at least to some extent. The first option would be to have large prime bounds and allowed number of large primes that follow the trend of previous factorization records. Then the number of survivors of sieving on one side is so large that it is not possible to use factorization trees on the other side, and we have to sieve on both sides. The other option is to reduce the number of large primes on the algebraic side (the more difficult side), so that after sieving on this side there are fewer survivors and we can use factorization trees. Of course, the number of relations per specialq will be reduced, but on the other hand the cost of finding them is reduced by about a factor of 2. In our RSA-240 computation, we found that neither option appeared to be definitively optimal, and after numerous simulations, we chose to apply the traditional strategy for the small qs (below the sieving bound lim) and the new strategy for the larger ones. 4.2 Distribution and parallelization For large computations such as the ones reported in this article, the relation collection step is a formidable computing effort, and it is also embarrassingly parallel: as computations for different special-qs are independent, a large number of jobs can run simultaneously, and need no inter-process communication. A large amount of computing power must be harnessed in order to complete this task in a reasonable amount of time. To this end, several aspects are crucially important. Distribution. First, the distribution of the work is seemingly straightforward. We may divide the interval [qmin , qmax ) into sub-intervals of any size we see fit, and have independent jobs process special-qs whose norm lie in these subintervals. This approach, however, needs to be refined if we use multiple computing facilities with inconsistent software (no common job scheduler, for instance), inconsistent hardware, and intermittent availability, possibly resulting in jobs frequently failing to complete. On several of the computing platforms we had access to, we used so-called best-effort jobs, that can be killed anytime by other users’ jobs. This approach means that it is necessary to keep track of all “work 11 RSA-240: 20 229.6 232.8 231 236 ,237 q lim1 lpb0,1 (prime) |Norm q| < lim1 : we allow |Norm q| > lim1 : 2 large primes on side 0, we allow 2 large primes on each side. 3 large primes on side 1. (q counts as an additional large prime on side 1.) We sieve on both sides. We sieve on side 1 and batch on side 0. DLP-240: 20 213 226.5 229 ,228 235 qi , qj lim0,1 (prime factors of q) lpb0,1 237.1 238.1 q (composite) q = qi qj We allow 2 large primes on each side. (The factors of q are not large primes.) We sieve on side 0 and batch on side 1. Fig. 4. Position of special-q ranges with respect to the sieving bounds lim and the large prime bounds lpb (values not to scale). For RSA-240, there are 2 distinct subranges with different kinds of relations that are sought, with different strategies. For DLP-240, the special-q range is well beyond the large prime bound, thanks to the use of composite special-qs. units” that have been assigned at any given point in time, and reliably collect all results from clients. For the computations reported in this article, the machinery implemented in Cado-NFS was sufficient. It consists of a standalone server where each work unit follows a state machine with the following states: AVAILABLE (a fresh work unit submitted for processing), ASSIGNED (when a client has asked for work), OK (result successfully uploaded to server), ERROR (result failed a sanity check on server, or client error), and CANCELED (work unit timed out, presumably because the client went offline). Work units that reach states ERROR or CANCELED are resubmitted up to a few times, to guard against potential infinite loops caused by software bugs. This approach was sufficient to deal with most computation mishaps, and the few remaining “holes” were filled manually. Parallelization. The second crucial aspect is parallelism. The lattice sieving algorithm that we use in relation collection is not, in itself, easy to parallelize. Furthermore, it is a memory-intensive computation that is quite demanding in terms of both required memory and memory throughput. In the most extreme case, having many CPU cores is of little help if the memory throughput is the limiting factor. The following (simplified) strategy was used to run the lattice sieving program at the whole machine level. 12 – Given the program parameters, determine the amount of memory m that is needed to process one special-q. On a machine with v virtual cores and memory M , determine the maximal number s of sub-processes and the number of threads t per sub-process such that sm ≤ M , st = v, and t is a meaningful subdivision of the machine. This strategy of maximizing s is meant to take advantage of coarse-grained parallelism. – Each of the s sub-processes is bound to a given set of t (virtual) cores of the machine, and handles one special-q at a time. For each special-q, sub-processes function as follows. First divide the set of p ∈ F for which we sieve (that is, whose norm is less than lim) into many slices based on several criteria (bounded slice size, constant value for ⌊log |Norm p|⌉, same number of conjugate ideals of p). The largest sieved prime ideals in F0 have somewhat rare hits (as in Figure 3(c)). We handle them with so-called “bucket sieving”, which proceeds in two phases that are parallelized differently: – “fill buckets”: slices are processed in parallel, and “updates” are precomputed and appended to several lists, one for each “region” of the sieve area. These lists are called “buckets”. A region is typically 64kB in size. In order to avoid costly concurrent writes, several independent sets of buckets can be written to by threads working on different slices. – “apply buckets”: regions are processed in parallel. This entails reading the information from “fill buckets”, that is, the updates stored in the different lists. Together with this second phase of the computation, we do everything that is easy to do at the region level: sieve small prime ideals, compute log |Res(a − bx, f0 )|, and determine whether the remaining cofactor is worth further examination. A rough approximation of the memory required by the above procedure is as follows, with #A denoting the size of the sieve area, and bounds 2I and lim being the two ends of the bucket-sieved range, as represented in Figure 5. X 1 . memory required ≈ #A × |Norm p| p∈F 0 p bucket-sieved ≈ #A × log log lim − log log 2I . The formula above shows that if bucket sieving is used as described above for prime ideals around 2I , which is not very large, the number of updates to store before applying them becomes a burden. To alleviate this, and deal with (comparatively) low-memory hardware, Cado-NFS can be instructed to do the “fill buckets” step above in several stages. Medium-size prime ideals (below a bound called bkthresh1, mentioned in Figure 5) are actually considered for only up to 256 buckets at a time. Updates for prime ideals above bkthresh1, on the other hand, are handled in two passes. This leads to: memory required ≈ #A × (log log lim − log log bkthresh1) #A + log log bkthresh1 − log log 2I ) . 256 13 20 2I bkthresh1 lpb lim p small size 1-level bucket sieve 2-level bucket sieve ECM extracted bucket sieve 0 2 lpb lim p product tree ECM extracted Fig. 5. Bucket sieve and product-tree sieve. Interaction with batch smoothness detection. If the algorithms inspired by [6] are used, the impact on distribution and parallelization must be considered. The cost analysis assumes that the product of the primes to be extracted has roughly the same size as the product of survivors to be tested. Only then can we claim a quasi-linear asymptotic complexity. In this context, a survivor is an (a, b) pair for which the sieving done on one side reveals a smooth or promising enough norm so that the norm on the other side will enter the batch smoothness detection. The situation depends on the number of survivors per special-q. In the DLP-240 case, the sieving parameters are chosen to reduce the size of the matrix. This has the consequence that the desired relations that are “high quality” relations are rare, so that the number of survivors per special-q is small (about 7000 per special-q, for #A = 231 ). In this setting, it makes sense to accumulate all the survivors corresponding to all the special-q of a work unit in memory, and handle them at the end. There are so few survivors that the cost of the batch smoothness detection remains small. This strategy deviates from the asymptotic analysis but works well enough, and does not interfere with the distribution techniques used by Cado-NFS. In the RSA-240 case, the situation is quite different. The number of survivors per special-q is high, so that the relative cost of the batch smoothness detection is non-negligible. It is therefore important to accumulate the correct number of survivors before starting to build the product trees. In our setting, this corresponds to between 100 and 200 special-qs, depending on their size. In order to keep the implementation robust to these variations and to a non-predefined work unit size, we had the sieving software print the survivors to files. A new file is started after a given number of survivors have been printed. This way, the processing can be handled asynchronously by other independent jobs. Again with simplicity and robustness in mind, we preferred to have the production and the processing of the survivors running on the same node, so as to avoid network transfers. Therefore the survivor files were stored on a local disk (or even on a RAM-disk for disk-less nodes). The next question is how to share the resources 14 on a single node, taking into account the fact that the top level of the product tree involves large integer multiplications, which do not parallelize efficiently, and yet consume a large amount of memory. After running some experiments, we found that nodes with at least 4GB of RAM per physical core could smoothly and efficiently accommodate the following setting: – One main job does the sieving on one side and continuously produces survivor files, each of them containing about 16M survivors. It uses as many threads as the number of logical cores on the node. In the parallelization strategy mentioned on page 12, only half of the RAM is considered available. – About half a dozen parallel jobs wait for survivor files to be ready, and then run the batch smoothness detection followed by the final steps required to write relations. Each of these jobs has an upper limit of (for example) 8 threads. The parallelization allows us to treat product trees and ECM curves in parallel, but each multiplication is single-threaded. We rely on the task scheduler of the operati