Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment
Open accessThe DOI matches its Crossref record; 32 of the 33 references it cites were found in a registry or an index.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
A Course in Computational Algebraic Number Theory
Cohen, H. (1993) · Graduate Texts in Mathematics · doi:10.1007/978-3-662-02945-9 · Cited by 2,567
The development of the number field sieve
(1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091534 · Cited by 574
Factorization of a 768-Bit RSA Modulus
Kleinjung, T., Aoki, K., Franke, J., Lenstra, A. K., Thomé, E., Bos, J. W., Gaudry, P., Kruppa, A., Montgomery, P. L., Osvik, D. A., et al. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_18 · Cited by 423
Self-citationSolving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
Coppersmith, D. (1994) · Mathematics of Computation · doi:10.2307/2153413 · Cited by 263
Factoring integers with the number field sieve
Buhler, J. P., Lenstra, H. W., & Pomerance, C. (1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091539 · Cited by 188
A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
Beckermann, B., & Labahn, G. (1994) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479892230031 · Cited by 184
Discrete logarithms and local units
Schirokauer, O. (1993) · Philosophical Transactions of the Royal Society of London. Series A: Physical and Engineering Sciences · doi:10.1098/rsta.1993.0139 · Cited by 133
Kaltofen, E. (1995) · Mathematics of Computation · doi:10.2307/2153451 · Cited by 132
Pollard, J. M. (1993) · Lecture notes in mathematics · doi:10.1007/bfb0091538 · Cited by 107
Joux, A., & Lercier, R. (2002) · Mathematics of Computation · doi:10.1090/s0025-5718-02-01482-5 · Cited by 93
The Middle Product Algorithm I
Hanrot, G., Quercia, M., & Zimmermann, P. (2004) · Applicable Algebra in Engineering Communication and Computing · doi:10.1007/s00200-003-0144-2 · Cited by 78
Self-citationOn polynomial selection for the general number field sieve
Kleinjung, T. (2006) · Mathematics of Computation · doi:10.1090/s0025-5718-06-01870-9 · Cited by 70
Thomé, E. (2002) · Journal of Symbolic Computation · doi:10.1006/jsco.2002.0533 · Cited by 67
Self-citationA Kilobit Special Number Field Sieve Factorization
Aoki, K., Frankē, J., Kleinjung, T., Lenstra, A. K., & Osvik, D. A. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-76900-2_1 · Cited by 53
Factorization Using the Quadratic Sieve Algorithm
Davis, J. A., & Holdridge, D. B. (1984) · Springer eBooks · doi:10.1007/978-1-4684-4730-9_9 · Cited by 49
Square roots of products of algebraic numbers
Montgomery, P. L. (1994) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/048/1314892 · Cited by 44
Polynomial selection for the number field sieve integer factorisation algorithm
Murphy, B. A. (1999) · doi:10.25911/5d6272199e44d · Cited by 40
A Kilobit Hidden SNFS Discrete Logarithm Computation
Fried, J., Gaudry, P., Heninger, N., & Thomé, E. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-56620-7_8 · Cited by 39
Self-citationAlgorithms for discrete logarithm in finite fields
Barbulescu, R. (2013) · theses.fr (ABES) · doi:10.70675/ecfaaf2fz2347z4a5dzb5d0z048ca56ebd70 · Cited by 33
Computation of a 768-Bit Prime Field Discrete Logarithm
Kleinjung, T., Diem, C., Lenstra, A. K., Priplata, C., & Stahlke, C. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-56620-7_7 · Cited by 29
Strategies in Filtering in the Number Field Sieve
Cavallar, S. (2000) · Lecture notes in computer science · doi:10.1007/10722028_11 · Cited by 28
Online order basis algorithm and its impact on the block Wiedemann algorithm
Giorgi, P., & Lebreton, R. (2014) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/2608628.2608647 · Cited by 21
Dumas, J., Kaltofen, E., Thomé, E., & Villard, G. (2016) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/2930889.2930908 · Cited by 17
Self-citationAdrian, D., Bhargavan, K., Durumeric, Z., Gaudry, P., Green, M., Halderman, J. A., Heninger, N., Springall, D., Thomé, E., Valenta, L., et al. (2018) · Communications of the ACM · doi:10.1145/3292035 · Cited by 16
Self-citationMersenne Factorization Factory
Kleinjung, T., Bos, J. W., & Lenstra, A. K. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45611-8_19 · Cited by 14
Algorithmes de logarithmes discrets dans les corps finis
Barbulescu, R. (2013) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 13
Bai, S., Bouvier, C., Kruppa, A., & Zimmermann, P. (2015) · Mathematics of Computation · doi:10.1090/mcom3048 · Cited by 11
Self-citationSquare Root Algorithms for the Number Field Sieve
Thomé, E. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31662-3_15 · Cited by 8
Self-citationFaster Cofactorization with ECM Using Mixed Representations
Bouvier, C., & Laurent Imbert, A. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45388-6_17 · Cited by 8
Parallel Structured Gaussian Elimination for the Number Field SievePreprint
Bouillaguet, C., & Zimmermann, P. (2019) · HAL · Cited by 7
Self-citationOn Improving Integer Factorization and Discrete Logarithm Computation using Partial Triangulation.Preprint
Boudot, F. (2017) · IACR Cryptology ePrint Archive · Cited by 4
Self-citationA new ranking function for polynomial selection in the number field sieve
David, N., & Zimmermann, P. (2020) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/754/15139 · Cited by 2
Self-citation
Research works printed but not linked: 2
- Kleinjung, T.: Polynomial selection. Slides presented at the CADO workshop on integer factorization (2008). http://cado.gforge.inria.fr/workshop/abstracts.html
- Lenstra, A.K., Lenstra Jr., H.W. (eds.): The Development of the Number Field Sieve. LNM, vol. 1554. Springer, Heidelberg (1993). https://doi.org/10.1007/BFb0091534 · DOI · Paper page
Cited by
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830
Quantum Algorithms: A Survey of Applications and End-to-end Complexities
Dalzell, A. M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gilyén, A., Hann, C. T., Kastoryano, M. J., Khabiboulline, E. T., Kubica, A., et al. (2023) · RWTH Publications (RWTH Aachen) · doi:10.18154/rwth-2026-02888 · Cited by 360
Experimental quantum secure network with digital signatures and encryption
Yin, H.-L., Fu, Y., Li, C.-L., Weng, C.-X., Li, B.-H., Gu, J., Lu, Y.-S., Huang, S., & Chen, Z.-B. (2023) · National Science Review · doi:10.1093/nsr/nwac228 · Cited by 214
Experimental authentication of quantum key distribution with post-quantum cryptography
Wang, L., Zhang, K., Wang, J., Cheng, J., Yang, Y., Tang, S.-B., Yan, D., Tang, Y.-L., Liu, Z., Yu, Y., et al. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00400-7 · Cited by 189
Quantum Algorithms: A Survey of Applications and End-to-end Complexities
Dalzell, A. M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gilyén, A., Hann, C. T., Kastoryano, M. J., Khabiboulline, E. T., Kubica, A., et al. (2025) · Cambridge University Press eBooks · doi:10.1017/9781009639651 · Cited by 146
Metadata
- Authors
- Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E., & Zimmermann, P.
- Affiliations
- XLIM (FR)
- Centre National de la Recherche Scientifique (FR)
- University of California San Diego (US)
- Corresponding author
- Boudot, Fabrice
- Gaudry, Pierrick
- Guillevic, Aurore
- Heninger, Nadia
- Thomé, Emmanuel
- Zimmermann, Paul
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer International Publishing
- Published
- 2020
- Volume
- 12171
- Pages
- 62-91
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W3034714558
- Cited by
- 71
- References
- 33
- Citations by year
- 2026: 5 · 2025: 9 · 2024: 15 · 2023: 17 · 2022: 9 · 2021: 10 · 2020: 6
- FWCI
- 7.96
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- www.springernature.com/gp/researchers/text-and-data-mining (tdm)
- www.springernature.com/gp/researchers/text-and-data-mining (vor)
- Locations
- Lecture notes in computer science (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- HAL (submittedVersion, other-oa)
- arXiv (Cornell University)
- Funders
- National Science Foundation (1651344)
- Cisco Systems
- University of Pennsylvania
- European Commission
- Partnership for Advanced Computing in Europe AISBL
- Ministère de l'Enseignement Supérieur et de la Recherche
- Centre National de la Recherche Scientifique
- Conseil Régional de Lorraine
- Topics
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Physical Sciences › Mathematics › Algebra and Number Theory › Analytic Number Theory Research
- Keywords
- integer factorization, discrete logarithm problem, prime fields, computational cost comparison
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.