zbMATH — the first resource for mathematics

Discrete logarithms: The effectiveness of the index calculus method. (English) Zbl 0895.11054
Cohen, Henri (ed.), Algorithmic number theory. Second international symposium, ANTS-II, Talence, France, May 18-23, 1996. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1122, 337-361 (1996).
Let \(G\) be a cyclic group generated by an element \(t\). The discrete logarithm problem is to compute for any \(b \in G\) the least non-negative integer \(e\) such that \(t^e = b\), or \({\log}_t (b) = e\). The recent developments on this problem are reviewed. Both the theoretical aspects of the many algorithms for it are considered as well as computational results for implementations of the algorithms. Three cryptographic protocols whose security depends on the difficulty of the discrete logarithm problem, namely the Diffie-Helman key exchange, the notion of public-key cryptography and digital signatures, are reviewed. The index calculus method for the discrete logarithm problem in the multiplicative group of a finite field is described and analyzed.
Both rigorous and heuristic subexponential algorithms are discussed. Implementations of the heuristic algorithms are considered, including the number field sieve (NFS) algorithm of Coppersmith-Odlyzko-Schroeppel for certain prime fields, and the Coppersmith algorithm for \(F_{2^n}\). Requisite linear algorithm for efficient implementation of these algorithms is given, with special reference to the NFS algorithm. Some aspects of the discrete logarithm problem on the class group of the imaginary quadratic order are considered. The index calculus method is also discussed in this setting, as well as some computational results on it. The paper concludes with some open questions on the discrete logarithm problem.
For the entire collection see [Zbl 0852.00023].

11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity
94A60 Cryptography