Linear complexity of the discrete logarithm (Q1869823)

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 \textit{C. Ding} and \textit{T. Helleseth} [On cyclotomic generator of order \(r\), Inf. Proc. Lett. 66, 21-25 (1998)], \textit{W. Meidl} and \textit{A. Winterhof} [IEEE Trans. Inf. Theory 47, 2807-2811 (2001; Zbl 1032.94004)], \textit{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 \textit{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)].