
Discrete Logarithms in GF(p)Aarion Bradford
Abstract: We wish to find the smallest nonnegative 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 BabyStep GiantStep algorithm, the Pollard Rho algorithm, the PohligHellman algorithm, and the IndexCalculus method. We show that, given certain assumptions about the smoothness of the integers, the index calculus will, in general, outperform the other three methods, subtantially increasing the range of problems which are feasible to solve. 