The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
Abstract
Recently, several algorithms using number field sieves have been given to factor a number n in heuristic expected time $L_n [1/3; c]$, where \[ L_n [ v ;c ] = \exp \left\{ ( c + o ( 1 ) ) ( \log n )^v ( \log \log n )^{1 - v } \right\} \] for $n \to \infty $. This paper presents an algorithm to solve the discrete logarithm problem for $GF ( p )$ with heuristic expected running time $L_p [ 1/3; 3^{2/3}]$. For umbers of a special form, there is an asymptotically slower but more practical version of the algorithm.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Factoring polynomials with rational coefficients
Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982) · Mathematische Annalen · doi:10.1007/bf01457454 · Cited by 4,018
Approximate formulas for some functions of prime numbers
Rosser, J. B., & Schoenfeld, L. (1962) · Illinois Journal of Mathematics · doi:10.1215/ijm/1255631807 · Cited by 1,546
Factoring Integers with Elliptic Curves
Lenstra, H. W. (1987) · The Annals of Mathematics · doi:10.2307/1971363 · Cited by 974
On Lovász’ lattice reduction and the nearest lattice point problem
Babai, L. (1986) · Combinatorica · doi:10.1007/bf02579403 · Cited by 938
Baker, A. (1975) · Cambridge University Press eBooks · doi:10.1017/cbo9780511565977 · Cited by 730
Solving sparse linear equations over finite fields
Wiedemann, D. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057137 · Cited by 546
On a problem of Oppenheim concerning “factorisatio numerorum”
Canfield, E. R., Erdös, P., & Pomerance, C. (1983) · Journal of Number Theory · doi:10.1016/0022-314x(83)90002-1 · Cited by 322
Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100295 · Cited by 285
Coppersmith, D., Odlzyko, A. M., & Schroeppel, R. (1986) · Algorithmica · doi:10.1007/bf01840433 · Cited by 271
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
Cited by
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
Guide to Elliptic Curve Cryptography
(2004) · Springer Professional Computing · doi:10.1007/b97644 · Cited by 3,054
The Elliptic Curve Digital Signature Algorithm (ECDSA)
Johnson, D., Menezes, A., & Vanstone, S. (2001) · International Journal of Information Security · doi:10.1007/s102070100002 · Cited by 2,239
Reducing elliptic curve logarithms to logarithms in a finite field
Menezes, A. J., Okamoto, T., & Vanstone, S. A. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.259647 · Cited by 1,022
A public-key infrastructure for key distribution in TinyOS based on elliptic curve cryptography
Malan, D. J., Welsh, M., & Smith, M. D. (2005) · 2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, 2004. IEEE SECON 2004. · doi:10.1109/sahcn.2004.1381904 · Cited by 712
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
The State of Elliptic Curve Cryptography
Koblitz, N., Menezes, A., & Vanstone, S. (2000) · Designs, Codes and Cryptography · doi:10.1023/a:1008354106356 · Cited by 685
The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes
Okamoto, T., & Pointcheval, D. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44586-2_8 · Cited by 477
Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice
Adrian, D., Bhargavan, K., Durumeric, Z., Gaudry, P., Green, M., Halderman, J. A., Heninger, N., Springall, D., Thomé, E., Valenta, L., et al. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813707 · Cited by 348
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344
Pairing-Based Cryptography at High Security Levels
Koblitz, N., & Menezes, A. (2005) · Lecture Notes in Computer Science · doi:10.1007/11586821_2 · Cited by 317
Modular Forms, a Computational Approach
Stein, W. (2007) · Graduate Studies in Mathematics · doi:10.1090/gsm/079 · Cited by 297
Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms
Roetteler, M., Naehrig, M., Svore, K. M., & Lauter, K. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-70697-9_9 · Cited by 212
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
Metadata
- Authors
- Gordon, D. M.
- Venue
- SIAM Journal on Discrete Mathematics
- Published
- 1993-02
- Volume
- 6
- Issue
- 1
- Pages
- 124-138
- ISSN
- 0895-4801 (ISSN-L)
- 1095-7146
- OpenAlex
- W1969728959
- Cited by
- 322
- References
- 18
- FWCI
- 36.07
- Type
- journal article
- Language
- en
- Open access
- closed
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.