An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)

A cryptographic system is described which is secure if and only if computing logarithms over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">GF(p)</tex> is infeasible. Previously published algorithms for computing this function require <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(p1/2)</tex> complexity in both time and space. An improved algorithm is derived which requires <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O =(log² p)</tex> complexity if <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p - 1</tex> has only small prime factors. Such values of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</tex> must be avoided in the cryptosystem. Constructive uses for the new algorithm are also described.