×

Discrete logarithms in finite fields and their cryptographic significance. (English) Zbl 0594.94016

Advances in cryptology, Proc. EUROCRYPT 84, Workshop Paris 1984, Lect. Notes Comput. Sci. 209, 224-314 (1985).
This article represents an extensive survey on computing discrete logarithms in finite fields and its relevance in cryptographic applications (mostly for public key cryptosystems).
Given a primitive element \(g\) of a finite field \(\mathrm{GF}(q)\), the discrete logarithm of a nonzero element \(u\) in \(\mathrm{GF}(q)\) is the integer \(k\), \(1\leq k\leq q-1\), with \(u=g^k\). Several algorithms for computing discrete logarithms are known, most of which are discussed in this paper (e.g. the index-calculus algorithm, and, in particular, the algorithm of D. Coppersmith [IEEE Trans. Inf. Theory 30, 587–594 (1984; Zbl 0554.12013)]). An estimate of the running time of (modifications of) this algorithm is given for fields \(\mathrm{GF}(2^n)\) which might actually be used in cryptography. It turns out that the values for \(n\) have to be at least 1500 and carefully chosen so that fields \(\mathrm{GF}(p)\), \(p\) prime, appear to offer a higher level of security, at least for \(p>2^{500}\).
[For the entire collection see Zbl 0578.00015.]

MSC:

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