Discrete Logarithms in GF(p)

Aarion Bradford

April 20th, at 3:30pm in K9509.

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.