A short proof for explicit formulas for discrete logarithms in finite fields. (English) Zbl 0726.11079

The author gives a very elegant and short proof of two explicit formulas for discrete logarithms. The first one was found by Mullen and White and the second one by Wells. The formula of Wells is generalized.


11T99 Finite fields and commutative rings (number-theoretic aspects)
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
Full Text: DOI


[1] Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Computing13, 850–864 (1984) · Zbl 0547.68046
[2] Chor, B., Rivest, R. L.: A knapsack type public key cryptosystem based on arithmetic in finite fields. Proc. CRYPTO 84, pp. 54–65. Lecture Notes in Computer Science, Vol.196. Berlin, Heidelberg, New York: Springer 1985 · Zbl 0571.94013
[3] Chor, B., Rivest, R. L.: A knapsack-type public key cryptosystem based on arithmetic in finite fields. IEEE Trans. Inform. Theory34, 901–909 (1988) · Zbl 0664.94011
[4] Coppersmith, D.: Methods and results in cryptography. Applications of Discrete Mathematics. Ringeisen, R. D., Roberts, F. S. (eds.), pp. 24–31. Philadelphia: SIAM 1988
[5] Coppersmith, D., Odlyzko, A. M., Schroeppel, R.: Discrete logarithms in GF(p). Algorithmica1, 1–15 (1986) · Zbl 0631.12010
[6] Lidl, R., Niederreiter, H.: Finite fields. Reading, MA: Addison-Wesley 1983 · Zbl 0554.12010
[7] Lidl, R., Niederreiter, H.: Introduction to finite fields and their applications. Cambridge: Cambridge University Press 1986 · Zbl 0629.12016
[8] Mullen, G. L., White, D.: A polynomial representation for logarithms in GF(q). Acta Arith.47, 255–261 (1986) · Zbl 0562.12018
[9] Odlyzko, A. M.: Discrete logarithms in finite fields and their cryptographic significance. Proc. EUROCRYPT 84, pp. 224–314. Lecture Notes in Computer Science, Vol.209. Berlin, Heidelberg, New York: Springer 1985 · Zbl 0594.94016
[10] Pomerance, C.: Fast, rigorous factorization and discrete logarithm algorithms. Discrete Algorithms and Complexity (Proc. Japan–US Joint Seminar, Kyoto, 1986), pp. 119–143. Boston: Academic Press 1987
[11] Wells, A. L., Jr.: A polynomial form for logarithms modulo a prime. IEEE Trans. Inform. Theory30, 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.