Generalizing the factoring-vs-discrete-logarithm hardness ratio: DSA-like primes beyond the 240-digit experiment

A 2020 paired record computation factored RSA-240 (795 bits) and solved a discrete logarithm in a 795-bit prime field on identical hardware, measuring that a safe-prime discrete logarithm costs about 3.3 times more core-years than factoring a number of the same size — far less than the folklore gap, but established only for safe primes and only at a single paired data point. What remains unresolved is what this ratio becomes for DSA-like primes, where discrete logarithms are computed in a small subgroup and the source predicts the ratio may drop to near or even below a factor of two without quantifying it. Quantifying the hardness ratio in this DSA-like setting is the open problem.

Background

Integer factoring and discrete logarithms in prime finite fields $\mathbb{F}_p$ are the two classical hardness assumptions behind RSA and finite-field Diffie–Hellman, DSA, and ElGamal. For large sizes, the best known algorithm for both problems is the number field sieve (NFS), a general algorithm with the same high-level structure: polynomial selection, relation collection (sieving for pairs whose norms are smooth, i.e. factor entirely into small primes), filtering, sparse linear algebra, and — only for discrete logarithms — a final individual-logarithm ("descent") step for the specific target. Both problems share the same heuristic asymptotic complexity of the form $L_N(1/3, c)$ (sub-exponential in the input size $N$), and in the practical range the constants effectively coincide, so the asymptotic formula alone cannot say which problem is harder.

In practice the costs differ for structural reasons. For factoring, the linear algebra works modulo 2; for discrete logarithms it works modulo the order $q$ of the target subgroup, and the matrix is typically larger and denser when $q$ is large. Conversely, polynomial selection for NFS-DL offers extra flexibility, and the expensive phases (relation collection and linear algebra) depend only on the prime $p$, not on the target. Whether discrete logarithms are "much harder" than factoring at a given size is therefore an empirical question.

The record history long suggested a large gap: RSA-768 (768 bits) was factored in 2009 (Kleinjung et al., 2010), while the first 768-bit prime-field discrete logarithm computation only followed in 2016 (Kleinjung, Diem, Lenstra, Priplata, Stahlke), at higher reported cost. In 2020, Boudot, Gaudry, Guillevic, Heninger, Thomé, and Zimmermann performed the first deliberately paired experiment: they factored RSA-240 (240 decimal digits, 795 bits) and computed a discrete logarithm modulo $p = \mathrm{RSA}\text{-}240 + 49204$, the smallest safe prime above RSA-240 (a safe prime is a prime $p = 2q+1$ with $q$ also prime, so the discrete-logarithm subgroup order $q$ is essentially as large as $p$), using the same hardware generation (all timings scaled to Intel Xeon Gold 6130 physical cores, counted in core-years — one core computing for one year) and the same open-source software (CADO-NFS). The totals were 953 core-years for the factoring (794 relation collection, 83 linear algebra) versus 3177 core-years for the discrete logarithm (2400 relation collection, 625 linear algebra): a ratio of only 3.3, where prior records had suggested a substantially larger gap.

The authors drew an explicit caveat on the scope of this ratio: it holds for safe primes. In the "DSA-like" situation — primes $p$ for which discrete logarithms are computed in a small subgroup of $\mathbb{F}_p^*$, as in the DSA signature standard (whose standardized parameter pairs $(L, N)$ for the bit lengths of $p$ and $q$ are $(1024, 160)$, $(2048, 224)$, $(2048, 256)$, and $(3072, 256)$; FIPS 186-4), where the small subgroup order $q$ makes the linear algebra cheaper and permits new trade-offs between relation collection and linear algebra — the ratio "is likely to drop, perhaps close to or maybe even below a factor of two", but they neither measured nor simulated it. Since the 3.3 value rests on a single 795-bit safe-prime data point and the source fixes no particular DSA-like parameter family, how the ratio varies with size and with the size of $q$ relative to $p$ remains unknown, and extrapolation is fragile: later refined analysis (Le Gluher, Spaenlehauer, Thomé, 2020) shows that the $o(1)$ term in the $L(1/3)$ formula converges only for astronomically large inputs and behaves erratically in the practical range, so asymptotic formulas cannot settle the trend.

The experiment also relied on methodological tools that remain experimental: an NFS simulator that predicts matrix sizes and phase costs before running a computation (building "fake relations" from real samples, applying a shrink factor to small parameters, and running a mini-filter), plus algorithmic variants — sieving by composite special-$q$ (batching the sieving around ideals with composite norm) and batch smoothness detection (testing many candidates for smoothness at once via product trees). The authors state that their "simulation machinery is still experimental" and that "a more systematic study is needed to validate this simulator and improve its precision", naming in particular a more sophisticated strategy for building fake relations based on a sample of real ones, and better handling of the columns corresponding to small very dense ideals under the shrink factor. The last page of the paper also reports the factorization of RSA-250 (829 bits, about 2700 core-years), with no matching discrete-logarithm computation at that size.

Problem Statement

Determine how the relative cost of computing discrete logarithms in a prime field $\mathbb{F}_p$ compares to the cost of factoring an integer of comparable size, as a function of prime-field structure — safe primes with a full-size subgroup order versus DSA-like primes with a small subgroup order $q$ — for which only the safe-prime regime has been measured. Concretely, the source question asks for:

1. A quantification of the factoring/discrete-logarithm hardness ratio in the DSA-like small-subgroup setting, where the cheaper linear algebra modulo a small $q$ permits re-optimized trade-offs between relation collection and linear algebra; the source predicts the safe-prime value of 3.3 drops to near or even below a factor of two, but this has never been measured or reliably simulated. The source fixes no particular DSA-like parameter family, and the trade-offs — hence the ratio — depend on the size of $q$ relative to $p$; the target scope is therefore fixed here to the four FIPS 186-4 parameter pairs $(L, N) = (1024, 160)$, $(2048, 224)$, $(2048, 256)$, $(3072, 256)$, or to an explicitly declared range of $q/p$ at a declared size, with the ratio over that declared scope carrying quantified uncertainty.

2. That the matrix sizes and phase costs underlying the ratio of item 1 be predicted with quantified error, at the input size and subgroup order used for item 1.

References

1. F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, P. Zimmermann, "Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment", Advances in Cryptology – CRYPTO 2020, LNCS 12171, 2020. DOI 10.1007/978-3-030-56880-1_3. https://doi.org/10.1007/978-3-030-56880-1_3 (also available as arXiv:2006.06197, DOI 10.48550/arXiv.2006.06197, and IACR ePrint 2020/697)
2. F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, P. Zimmermann, "The State of the Art in Integer Factoring and Breaking Public-Key Cryptography", IEEE Security & Privacy 20(2), 2022. DOI 10.1109/MSEC.2022.3141918. https://doi.org/10.1109/MSEC.2022.3141918 (also available as HAL hal-03691141)
3. N. P. Smart, E. Thomé, "History of Cryptographic Key Sizes", in Computational Cryptography, Cambridge University Press, 2021. DOI 10.1017/9781108854207.014. https://doi.org/10.1017/9781108854207.014 (also available as IACR ePrint 2021/894, https://eprint.iacr.org/2021/894)
4. A. Le Gluher, P.-J. Spaenlehauer, E. Thomé, "Refined Analysis of the Asymptotic Complexity of the Number Field Sieve", 2020. DOI 10.48550/arXiv.2007.02730. https://arxiv.org/abs/2007.02730 (accepted in Mathematical Cryptology)
5. 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, P. Zimmermann, "Factorization of a 768-Bit RSA Modulus", Advances in Cryptology – CRYPTO 2010, 2010. DOI 10.1007/978-3-642-14623-7_18. https://doi.org/10.1007/978-3-642-14623-7_18
6. T. Kleinjung, C. Diem, A. K. Lenstra, C. Priplata, C. Stahlke, "Computation of a 768-bit prime field discrete logarithm", IACR ePrint 2017/067, 2017. https://eprint.iacr.org/2017/067
7. G. De Micheli, P. Gaudry, C. Pierrot, "Lattice Enumeration and Automorphisms for Tower NFS: A 521-Bit Discrete Logarithm Computation", Journal of Cryptology, 2023. DOI 10.1007/s00145-023-09487-x. https://doi.org/10.1007/s00145-023-09487-x (also available as IACR ePrint 2021/707, https://eprint.iacr.org/2021/707)
8. H. Al Aswad, C. Pierrot, "Individual discrete logarithm with sublattice reduction", Designs, Codes and Cryptography, 2023. DOI 10.1007/s10623-023-01282-w. https://doi.org/10.1007/s10623-023-01282-w
9. H. Al Aswad, E. Thomé, C. Pierrot, "Discrete Logarithm Factory", IACR Communications in Cryptology 1(3), 2024. DOI 10.62056/ah2ip2fgx. https://doi.org/10.62056/ah2ip2fgx
10. C. Bouillaguet, A. Fleury, P.-A. Fouque, P. Kirchner, "We Are on the Same Side. Alternative Sieving Strategies for the Number Field Sieve", Advances in Cryptology – ASIACRYPT 2023, 2023. DOI 10.1007/978-981-99-8730-6_5. https://doi.org/10.1007/978-981-99-8730-6_5 (also available as IACR ePrint 2023/801, https://eprint.iacr.org/2023/801)
11. C. Bouillaguet, "Nice Attacks — but What is the Cost? Computational Models for Cryptanalysis", IACR ePrint 2022/197, 2022. https://eprint.iacr.org/2022/197
12. National Institute of Standards and Technology, "Digital Signature Standard (DSS)", FIPS 186-4, 2013. https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf (DSA parameter pairs $(L, N)$ in §4.2; superseded by FIPS 186-5)