Discrete Logarithms in GF(p)
Abstract: We wish to find the smallest non-negative integer, r, for which b = a^r where a and b are in GF(p) (if such an r exists). This is the discrete logarithm problem (DLP). A number of strategies have been proposed to solve the DLP, among them, Shanks Baby-Step Giant-Step algorithm, the Pollard Rho algorithm, the Pohlig-Hellman algorithm, and the Index-Calculus method. We show that, given certain assumptions about the smoothness of the integers, the index calculus will, in general, out-perform the other three methods, subtantially increasing the range of problems which are feasible to solve.