×

The discrete logarithm problem. (English) Zbl 0734.11073

Cryptology and computational number theory, Lect. Notes AMS Short Course, Boulder/CO (USA) 1989, Proc. Symp. Appl. Math. 42, 49-74 (1990).
Let \(G\) be a multiplicative group and for \(g\in G\), \(<g>\) the cyclic group generated by \(g\). The discrete logarithm problem is then, given \(a\in <g>\) find \(x\) such that \(g^x=a\). Applications of this problem as a one way function to cryptography, such as the common key construction of Diffie and Hellman, are noted. The computational complexity of this problem is considered with the known algorithms in three situations discussed:
(i) for arbitrary groups where specific properties of the group are not used (Shank’s algorithm),
(ii) for finite groups of smooth order (Pohlig-Hellman algorithm) and
(iii) techniques that exploit methods of representing elements as products of elements from a small subset (index calculus algorithms).
Sections on finite fields of prime characteristic and characteristic two consider special techniques that may be used in these cases. The paper concludes with some open questions and a challenge to break a secret key based on a particular discrete logarithm problem.
[For the entire collection see Zbl 0722.00005.]

MSC:

11Y16 Number-theoretic algorithms; complexity
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94A60 Cryptography

Citations:

Zbl 0722.00005