An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)
S.C. Pohlig, Martin E. Hellman · IEEE Transactions on Information Theory · 1978
A cryptographic system is described which is secure if and only if computing logarithms overGF(p)is infeasible. Previously published algorithms for computing this function requireO(p^{1/2})complexity in both time and space. An improved algorithm is derived which requiresO =(\log^{2} p)complexity ifp - 1has only small prime factors. Such values ofpmust be avoided in the cryptosystem. Constructive uses for the new algorithm are also described.