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

IEEE Transactions on Information TheoryPublished 1 January 1978

S.C. Pohlig, Martin E. Hellman

DOI10.1109/tit.1978.1055817

Source URL

Citations1,186

SJR quartileQ1

SJR score1.46

SNIP1.76

TL;DR

An improved algorithm is derived which requires O =(\log^{2} p) complexity if p - 1 has only small prime factors and such values of p must be avoided in the cryptosystem.

Abstract

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 =(\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.

Keywords

Computer Science

IEEE Transactions on Information TheoryNew directions in cryptography

14,441 Citations1976Whitfield Diffie, Martin E. Hellman

IBM Journal of Research and DevelopmentIrreversibility and Heat Generation in the Computing Process

4,864 Citations1961Rolf Landauer

IBM Journal of Research and DevelopmentIrreversibility and heat generation in the computing process

2,613 Citations2000Rolf Landauer

Two simple, but representative, models of bistable devices are subjected to a more detailed analysis of switching kinetics to yield the relationship between speed and energy dissipation, and to estimate the effects of errors induced by thermal fluctuations.

Communications of the ACMSecure communications over insecure channels

744 Citations1978Ralph C. Merkle

This paper shows that it is possible to select a key over open communications channels in such a fashion that communications security can be maintained, and describes a method which forces any enemy to expend an amount of work which increases as the square of the work required of the two communicants to select the key.

View PDF

Proceedings of the IEEEPhysical limits in digital electronics

300 Citations1975Robert W. Keyes

Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)On Digital Signatures and Public-Key Cryptosystems.

177 Citations1977Ronald L. Rivest, Adi Shamir +1 more

It is shown that the single operation of raising a number to a fixed power modulo a composite modulus is sufficient to implement digital signatures: a way of creating for a (digitized) document a recognizable, unforgeable, document-dependent digitized signature whose authenticity the signer can not later deny.

Communications of the ACMA user authentication scheme not requiring secrecy in the computer

175 Citations1974Arthur V. Evans, William Kantrowitz +1 more

A password scheme is presented which does not require secrecy in the computer and is based on using a function H which the would-be intruder is unable to invert.

View PDF

Communications of the ACMA high security log-in procedure

140 Citations1974George Purdy

It is suggested that for the protection of time sharing systems from unauthorized users polynomials over a prime modulus are superior to one-way ciphers derived from Shannon codes.

View PDF