## 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=g^{x} 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 Z_{p}* 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 Z_{p}* 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.