An improved algorithm for computing logarithms overand its cryptographic significance (Corresp.)
S Pohlig, M Hellman - IEEE Transactions on information Theory, 1978 - ieeexplore.ieee.org
S Pohlig, M Hellman
IEEE Transactions on information Theory, 1978•ieeexplore.ieee.orgA 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=(\log^{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.
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=(\log^{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.
A cryptographic system is described which is secure if and only if computing logarithms over is infeasible. Previously published algorithms for computing this function require complexity in both time and space. An improved algorithm is derived which requires complexity if has only small prime factors. Such values of must be avoided in the cryptosystem. Constructive uses for the new algorithm are also described.
ieeexplore.ieee.org