Abstract
In this paper we present a new, heuristic method for computing logarithms overGF(2p). When 2p−1 is a Mersenne prime ≦231−1 it works in very short running times on a general purpose computer. It is based on the interdependent relations
and
, wheref andf rs are polynomials overGF(2).
Its cryptographic significance is discussed and it can be considered as an attempt to swindle MITRE Corporation which reportedly is using a public key distribution system, based on the presumed difficulty in computing logarithms overGF(2127).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
W. Diffie and M. Hellman,New directions in cryptography, IEEE Trans. on inform. th., IT-22 (1976), pp. 644–654.
S. Pohlig and M. Hellman,An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. on inform. th., IT-24 (1978), pp. 106–110.
S. Pohlig,Algebraic and combinatoric aspects of cryptography, Ph. D. Dissertation, Stanford University, 1978.
S. Berkovits, J. Kowalchuk and B. Schanning,Implementing public key scheme, IEEE Commun. Mag., 17, May 1979, pp. 2–3.
L. Adleman,A subexponential algorithm for the discrete logarithm problem with applications to cryptography, MIT/LCS 1979. (Working abstract).
G. H. Hardy and E. M. Wright,An Introduction to the Theory of Numbers, 5th ed., Oxford, 1979, p. 358.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Herlestam, T., Johannesson, R. On computing logarithms overGF(2p). BIT 21, 326–334 (1981). https://doi.org/10.1007/BF01941467
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01941467