This paper considers the computational complexity of the discrtte logarithm and related problems in the ocntext of "generic algorithms"-that is, algorithms which do not exploit any special properties of the encodings of group elements, other than the property that each group element is encoded as a unique binary string. Lower bounds on the complexity of these problems are proved that match the known upper bounds: any generic algorithm must perform OMEGA(p~1/2) group operations, where p is the largest prime dividing the order of the group. Also, a new method for correcting a fauley Diffie-Hellman oracle is presented.
展开▼
