Odlyzko, A. M. 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.] Reviewer: Willi Meier (Brugg) Cited in 5 ReviewsCited in 55 Documents MSC: 94A60 Cryptography 11T71 Algebraic coding theory; cryptography (number-theoretic aspects) 11T06 Polynomials over finite fields 11Y16 Number-theoretic algorithms; complexity Keywords:survey; public key cryptosystems; algorithms; cryptography Citations:Zbl 0578.00015; Zbl 0554.12013 × Cite Format Result Cite Review PDF