Abstract
Consider the finite field having q elements and denote it by GF(q). Let α be a generator for the nonzero elements of GF(q). Hence, for any element b≠0 there exists an integer x, 0≤x≤q−2, such that b=αx. We call x the discrete logarithm of b to the base α and we denote it by x=log α b and more simply by log b when the base is fixed for the discussion. The discrete logarithm problem is stated as follows:
Find a computationally feasible algorithm to compute log α b for any b∈GF(q), b≠0.
Research supported in part by the Department of Communications under Contract # 20ST 36001-4-0853.
Chapter PDF
Similar content being viewed by others
Keywords
- Authentication Scheme
- Discrete Logarithm
- Irreducible Polynomial
- Random Integer
- Discrete Logarithm Problem
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
L.M. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, Proc. 20th IEEE Found. Comp. Sci. Symp. (1979), 55–60.
B. Arazi, Sequences constructed by operations modulo 2n−1 or mod 2n and their application in evaluating the complexity of a log operation over GF(2n), preprint.
I.F. Blake, R. Fuji-Hara, R.C. Mullin and S.A. Vanstone, Computing logarithms in finite fields of characteristic two, SIAM J. Alg. Disc. Methods. Vol. 5 #2 (1984), 276–285.
I.F. Blake, R. Fuji-Hara, R.C. Mullin and S.A. Vanstone, Finite field-techniques for shift registers with applications to ranging problems and cryptography, Final Report Project #106-16-02, Department of Communications (1983).
I.F. Blake, R. Fuji-Hara, R.C. Mullin and S.A. Vanstone,An attack on the discrete logarithm problem in GF(2127), Progress Report, Project #106-16-02, Department of Communications (1982).
D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory., (July 1984), 587–594.
W. Diffie and M.E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory., IT-22 (1976), 644–654.
T. ElGamel, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory. to appear.
T. Herlestam and R. Johanneson, On computing logarithms over GF(2p), BIT 21 (1981), 326–334.
D.E. Knuth The Art of Computer Programming: Vol. 2. Seminumerical Algorithms. 2nd ed. Addison-Wesley 1981.
D.L. Long and A. Wigderson, How discreet is the discrete log? Proc. 15th ACM Symp. Theory of Computing (1983), 413–420.
R.C. Mullin, E. Nemeth and N. Weidenhofer, Will public key crypto systems live up to their expectations? HEP implementation of the discrete log codebreaker, preprint.
A. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Eurocrypt-84 (to appear).
S.C. Pohlig and M. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), 106–110.
B.P. Schanning, Data encryption with public key distribution, EASCON Conf. Rec., Washington D.C., October 1979, 653–660.
A.E. Western and J.C.P. Miller, Tables of indices and primitive roots, Royal Society Mathematical Tables. Cambridge University 9 (1968).
K. Yiu and K. Peterson, A single-chip VLSI implementation of the discrete exponential public key distribution system, Proc. GLOBECOM-82, IEEE (1982), 173–179.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1985 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blake, I.F., Mullin, R.C., Vanstone, S.A. (1985). Computing Logarithms in GF (2n). In: Blakley, G.R., Chaum, D. (eds) Advances in Cryptology. CRYPTO 1984. Lecture Notes in Computer Science, vol 196. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39568-7_8
Download citation
DOI: https://doi.org/10.1007/3-540-39568-7_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-15658-1
Online ISBN: 978-3-540-39568-3
eBook Packages: Springer Book Archive