PROBLEM LINK:
Author, Tester, Editorialist: Vaibhav Gupta
PROBLEM
Solve the Discrete Logarithm Problem.
QUICK EXPLANATION
Given y, g and p find the smallest x such that y=gx mod p
EXPLANATION
The hardness of finding discrete logarithms depends on the groups. For example, a popular choice of groups for discrete logarithm based crypto-systems is Zp* where p is a prime number. However, if p−1 is a product of small primes, then the Pohlig–Hellman algorithm can solve the discrete logarithm problem in this group very efficiently. That’s why we always want p to be a safe prime when using Zp* as the basis of discrete logarithm based crypto-systems. A safe prime is a prime number which equals 2q+1 where q is a large prime number. This guarantees that p-1 = 2q has a large prime factor so that the Pohlig–Hellman algorithm cannot solve the discrete logarithm problem easily. Even p is a safe prime, there is a sub-exponential algorithm which is called the index calculus. That means p must be very large (usually at least 1024-bit) to make the crypto-systems safe. In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm for computing the discrete logarithm.