China
Africa
Explore chapters and articles related to this topic
Discrete Logarithm Problem
Published in Khaleel Ahmad, M. N. Doja, Nur Izura Udzir, Manu Pratap Singh, Emerging Security Algorithms and Techniques, 2019
Khaleel Ahmad, Afsar Kamal, Khairol Amali Bin Ahmad
As mentioned above, finding the remainder through modulus is easy but doing its inverse to get logarithm is very difficult. To solve this problem, the baby-step giant-step algorithm introduced by Shanks is one of the most popular algorithms that deal with discrete logarithm in any finite abelian group. This algorithm is widely used in many applications of computational theory and invariants of the elliptic curve factorization techniques. It is a time-memory trade-off method with complexity O(n) group multiplication. This algorithm works on any cyclic group G with n order to reduce the time at the cost of extra storage (Kushwaha & Mahalanobis, 2017).
Number Theory
Published in Paul L. Goethals, Natalie M. Scala, Daniel T. Bennett, Mathematics in Cyber Research, 2022
The baby-step giant-step algorithm is a general-purpose algorithm that solves the discrete logarithm problem in any cyclic group. It is a meet-in-the-middle type algorithm, which seeks to find a collision between two sequences.
Linear Algebra on Parallel Structures Using Wiedemann Algorithm to Solve Discrete Logarithm Problem
Published in IETE Journal of Research, 2022
K S Spoorthi, R. Padmavathy, S K Pal, S Ravi Chandra
The baby-step/giant-step algorithm: Shanks in 1971 [5] gave a method to solve DLP [1], which works for all finite cyclic groups. The running time of the algorithm and the space complexity is , which is definitely an improvement over, brute force method with complexity. Yet even this is exponential in nature.Pohlig–Hellman algorithm: Pohlig and Hellman in 1978 [6] introduced a new method to solve DLP. Pohlig–Hellman can be used for finite group of prime order. Its worst case complexity is the same as the baby-step/giant-step algorithm. But otherwise, if there is a possibility of prime factorization of n (order of the group), as , the complexity can be given by Pollard Rho algorithm: Pollard, Monte Carlo [7] introduced Pollard Rho. The Pollard Rho is another method for solving DLP, the complexity is given by . When combined with Pohlig–Hellman it gives the complexity , where p is the highest factor in the factorization of n.Index Calculus Method (ICM): Index Calculus is one of the powerful algorithms proposed to solve discrete logarithms. Many methods like Number Field Sieve (NFS) and Function Field Sieve (FFS) belong to Index Calculus family. ICM is applicable for a group, G of prime order n and generator g. The first step in Index Calculus involves selection of factor base elements, which is basically a set of primes () belongs to the Group G. The relations are formulated as shown in Equation (1)