A note on discrete logarithms in finite fields. (English) Zbl 0749.11055

Let \(F_ q\) denote the finite field of order \(q\), \(q=p^ n\geq 3\), \(p\) prime and \(F^*_ q\) the cyclic multiplicative group of nonzero elements. If \(\alpha\in F^*_ q\) is primiitve, the discrete logarithm of \(\beta\in F^*_ q\) to base \(\alpha\) is the unique integer \(x\) such that \(\beta=\alpha^ x\). It was previously shown that for \(q=p\) a prime \[ \log_ \alpha\beta=\sum^{p-2}_{i=1}(1-\alpha^ i)^{-1}\beta^ i. \] This note generalizes this formula to cases where the base is not necessarily a primitive element and to prime power fields.


11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94A60 Cryptography
Full Text: DOI


[1] Lidl, R., Niederreiter, H.: Finite Fields, Encyclo. Math. Appls., Vol. 20. Addison-Wesley, Reading, MA 1983. (Now distributed by Camb. Univ. Press) · Zbl 0554.12010
[2] Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications. Cambridge: Camb. Univ. Press 1986 · Zbl 0629.12016
[3] Mullen, G. L., White, D.: A polynomial representation for logarithms in GF(q). Acta Arith.47, 255-261 (1986) · Zbl 0562.12018
[4] Niederreiter, H.: A short proof for explicit formulas for discrete logarithms in finite fields. App. Alg. Eng. Comm. Comp.1, 55-57 (1990) · Zbl 0726.11079
[5] Odlyzko, A. M.: Discrete logarithms in finite fields and their cryptographic significance. Proc. EUROCRYPT, Vol. 84, pp. 224-314. Lect. Notes in Comp. Sci., Vol. 209. Berlin, Heidelberg, New York: Springer 1985 · Zbl 0594.94016
[6] Pollard, J. M.: The fast Fourier transform in a finite field. Math. Computation25, 365-374 (1971) · Zbl 0221.12015
[7] Wells, A. L., Jr.: A polynomial form for logarithms modulo a prime. IEEE Trans. Inform. TheoryIT-30, 845-846 (1984) · Zbl 0558.12009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.