Linear complexity of the discrete logarithm. (English) Zbl 1024.11078

The authors prove several lower bounds on the linear complexity of finite sequences consisting of consecutive values of the discrete logarithm modulo a prime. The method and the results are new and deserve highest notice in mathematical cryptography. In particular, several previously known results are improved. For complementary results on the linear complexity of the discrete logarithm see C. Ding and T. Helleseth [On cyclotomic generator of order \(r\), Inf. Proc. Lett. 66, 21-25 (1998)], W. Meidl and A. Winterhof [IEEE Trans. Inf. Theory 47, 2807-2811 (2001; Zbl 1032.94004)], I. Shparlinski [Number theoretic methods in cryptography. Complexity lower bounds. Progress in Computer Science and Applied Logic. 17. Basel: Birkhäuser (1999; Zbl 0912.11057)], and I. Shparlinski [Cryptographic applications of analytic number theory. Complexity lower bounds and pseudorandomness. Progress in Computer Science and Applied Logic. 22. Basel: Birkhäuser (2003; Zbl 1036.94001)].


11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
94A60 Cryptography
Full Text: DOI