On the feasibility of computing discrete logarithms using Adleman's subexponential algorithm
Abstract
Some public key distribution systems, based on the difficulties in computing logarithms modulo a large prime, have been alleged to be insecure because of a statement that any logarithm modulo a 200 bit prime can be computed within a reasonable time by means of a subexponential algorithm due to Adleman.In this commentary said algorithm is examined from an algebraic and number-theoretical point of view. The scrutiny shows that the algebraic model for the algorithm contains several traps which seem to be hard to circumvent, and also, not least, that the presupposed abundance of so called round numbers will not be at hand in the computationally interesting cases.Hence it is concluded that the algorithm cannot be a serious threat to the mentioned public key distribution systems.
References
[1]
L. Adleman: "A subexponential algorithm for the discrete logarithm problem with applications to cryptography" (Working abstract), MIT/LCS, 1979. A shortened and slightly altered version appeared in Proc 20th IEEE Symp on Found of Comp Sci, Oct 1979, p 55--60.
[2]
T. Herlestam and R. Johannesson: "On computing logarithms over GF (2P)", BIT 21 (1981), 326--334.
[3]
G. H. Hardy and E. M. Wright: An Introduction to the Theory of Numbers, 5th ed, Oxford, 1979.
[4]
R. A. Rankin: "The difference between consecutive prime numbers", J London Math Soc 13 (1938), 242--247.
[5]
N. G. deBruijn: "On the number of positive integers ≤ x and free of prime factors > y", Indag Math 13 (1951), 50--60.
[6]
N. G. deBruijn: "On the number of positive integers ≤ x and free of prime factors > y, II", Indag Math 28 (1966), 239--247.
[7]
V. Ennola: "On numbers with small prime divisors", Ann Acad Sci Fennicae (A) I, 440 (1969), 1--16.
[8]
H. Halberstam: "On integers all of whose prime factors are small", Proc London Math Soc (3) 21 (1970), 102--107.
[9]
A. G. Konheim: Cryptography, A Primer, Wiley, New York (1981).
[10]
M. Morrison and J. Brillhart: "A method of factoring and the factorization of F7", Math Comp 29 (1975), 183--205.
[11]
J. D. Dixon: "Asymptotically fast factorization of integers", Math Comp 36 (1981), 255--260.
[12]
J. P. Burg and D. C. Campbell: "Secure voice communication over the public switched network using public key distribution systems", Intelcon 1979 Exp Proc, Dallas 1979, 23--25.
[13]
D. B. Hovden and L. G. Muret: "User oriented voice security", Intelcon 1979 Exp Proc, Dallas, 1979, 8--9.
Recommendations
A Subexponential Algorithm for Discrete Logarithms over All Finite Fields
CRYPTO '93: Proceedings of the 13th Annual International Cryptology Conference on Advances in CryptologyThere are numerous subexponential algorithms for computing discrete logarithms over certain classes of finite fields. However, there appears to be no published subexponential algorithm for computing discrete logarithms over all finite fields. We present ...
On Computing Logarithms Over Finite Fields
CRYPTO '85: Advances in CryptologyThe problem of computing logarithms over finite fields has proved to be of interest in different fields [4]. Subexponential time algorithms for computing logarithms over the special cases GF(p), GF(p 2) and GF(p m) for a fixed p and m have been ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1983 Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 January 1983
Published in SIGACT Volume 15, Issue 1
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 152Total Downloads
- Downloads (Last 12 months)17
- Downloads (Last 6 weeks)4
Reflects downloads up to 22 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in