An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)
Abstract
A cryptographic system is described which is secure if and only if computing logarithms overGF(p)is infeasible. Previously published algorithms for computing this function requireO(p^{1/2})complexity in both time and space. An improved algorithm is derived which requiresO =(\log^{2} p)complexity ifp - 1has only small prime factors. Such values ofpmust be avoided in the cryptosystem. Constructive uses for the new algorithm are also described.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
If r is composite, the discrete logarithm problem may be decomposed into problems in subgroups of orders dividing r.
“If r is composite, the discrete logarithm problem may be decomposed into problems in subgroups of orders dividing r , as shown by Pohlig and Hellman [68].”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as Pohlig and Hellman [68]
Cites
Secure communications over insecure channels
Merkle, R. C. (1978) · Communications of the ACM · doi:10.1145/359460.359473 · Cited by 757 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713 · see citing works
Self-citationA method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462 · see citing works
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 · see citing works
A public key cryptosystem and a signature scheme based on discrete logarithms
Elgamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057074 · Cited by 8,059 · see citing works
The Arithmetic of Elliptic Curves
Silverman, J. H. (1986) · Graduate Texts in Mathematics · doi:10.1007/978-1-4757-1920-8 · Cited by 4,044 · see citing works
Privacy-preserving data publishing: A survey of recent developments
Fung, B. C. M., Wang, K., Chen, R., & Yu, P. S. (2010) · ACM Computing Surveys · doi:10.1145/1749603.1749605 · Cited by 1,704 · see citing works
A Simple Unpredictable Pseudo-Random Number Generator
Blum, L., Blum, M., & Shub, M. (1986) · SIAM Journal on Computing · doi:10.1137/0215025 · Cited by 1,036 · see citing works
Tools for privacy preserving distributed data mining
Clifton, C., Kantarcioglu, M., Vaidya, J., Lin, X., & Zhu, M. Y. (2002) · ACM SIGKDD Explorations Newsletter · doi:10.1145/772862.772867 · Cited by 890 · see citing works
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 · see citing works
Strong password-only authenticated key exchange
Jablon, D. P. (1996) · ACM SIGCOMM Computer Communication Review · doi:10.1145/242896.242897 · Cited by 532 · see citing works
Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
Ekerå, M. (2021) · Journal of Mathematical Cryptology · doi:10.1515/jmc-2020-0006 · Cited by 3 · see citing works
- Authors
- Pohlig, S., & Hellman, M.
- Affiliations
- MIT Lincoln Laboratory (US)
- Stanford University (US)
- ORCID
- Hellman, M.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1978-01
- Volume
- 24
- Issue
- 1
- Pages
- 106-110
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W1981455414
- Cited by
- 1,199
- References
- 1
- Citations by year
- 2026: 5 · 2025: 25 · 2024: 19 · 2023: 17 · 2022: 25 · 2021: 47 · 2020: 30 · 2019: 26 · 2018: 30 · 2017: 24 · 2016: 35 · 2015: 36 · 2014: 39 · 2013: 45 · 2012: 50
- FWCI
- 43.61
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
- Keywords
- discrete logarithm problem, finite field GF(p), algorithmic complexity, cryptographic security, ciphers
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
