Discrete logarithms: The effectiveness of the index calculus method
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].
- Discrete logarithm problem using index calculus method
- Discrete logarithms: Recent progress
- Computing discrete logarithm by interval-valued paradigm
- Computing discrete logarithms
- Indiscreet discrete logarithms
- Discrete logarithms: The past and the future
- Computing Prime Factorization And Discrete Logarithms: From Index Calculus To Xedni Calculus
- On Search Complexity of Discrete Logarithm
- Computation of discrete logarithms in an arbitrary finite field
- A serial version of the Pohlig-Hellman algorithm for computing discrete logarithms
- Function field sieve method for discrete logarithms over finite fields
- Cubic sieve congruence of the discrete logarithm problem, and fractional part sequences
- Speeding up exponentiation using an untrusted computational resource
- The discrete logarithm problem
- Extended explicit relations between trace, definition field, and embedding degree
- Local duality and the discrete logarithm problem
- A simple generalization of the ElGamal cryptosystem to non-abelian groups. II
- Discrete logarithm problem in GH and XTR scheme
- Performance analysis of index calculus method
- Elementary thoughts on discrete logarithms
- scientific article; zbMATH DE number 3956969 (Why is no real title available?)
- An algorithm for evaluation of discrete logarithms in some nonprime finite fields
- scientific article; zbMATH DE number 691483 (Why is no real title available?)
- Discrete logarithm problem using index calculus method
- scientific article; zbMATH DE number 2145147 (Why is no real title available?)
- Computing Prime Factorization And Discrete Logarithms: From Index Calculus To Xedni Calculus
- Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
- Computing the multiplicative group of residue class rings
- Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms
- Using number fields to compute logarithms in finite fields
- A hidden number problem in small subgroups
- Computing the characteristic polynomials of a class of hyperelliptic curves for cryptographic applications
- On the cubic sieve method for computing discrete logarithms over prime fields
- Algorithmic Number Theory
- A review on the isomorphism classes of hyperelliptic curves of genus 2 over finite fields admitting a Weierstrass point
- Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity
This page was built for publication: Discrete logarithms: The effectiveness of the index calculus method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4375624)
