An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)
Stephen 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.
Cited by 1,193 works. doi:10.1109/tit.1978.1055817
Authors
References
- New directions in cryptography
- Secure communications over insecure channels
- Time-Sharing Computer Systems
- A user authentication scheme not requiring secrecy in the computer
- A high security log-in procedure
- Irreversibility and Heat Generation in the Computing Process
- The Art of Computer Programming. Vol. II: Seminumerical Algorithms
- Irreversibility and heat generation in the computing process
- Physical limits in digital electronics
- Time-Sharing Computer Systems