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

Abstract

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(p^{1/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^{2} 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.