Computation of Discrete Logarithms in Prime Fields

If p is a prime and g and x integers, then computation of y such that 1.1$$ y \equiv g^x \bmod p,0 \leqslant y \leqslant p - 1 $$ is referred to as discrere exponentiarion. Using the successive squaring method, it is very fast (polynomial in the number of bits of ∣p∣ + ∣g∣ + ∣x∣). On the other hand, the inverse problem, namely, given p, g, and y, to compute some z such that Equation 1.1 holds, which is referred to as the discrete logarithm problem, appears to be quite hard in general. Many of the most widely used public key cryptosystems are based on the assumption that discrete logarithms are indeed hard to compute, at least for carefully chosen primes.