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 GF (p) is infeasible. Previously published algorithms for computing this function require O (p^1/2) complexity in both time and space. An improved algorithm is derived which requires O = (^2 p) complexity if p - 1 has only small prime factors. Such values of p must be avoided in the cryptosystem. Constructive uses for the new algorithm are also described.