A note on the linear complexity profile of the discrete logarithm in finite fields. (English) Zbl 1063.11052

Feng, Keqin (ed.) et al., Coding, cryptography and combinatorics. Basel: Birkhäuser (ISBN 3-7643-2429-5/hbk). Progress in Computer Science and Applied Logic 23, 359-367 (2004).
For an integer \(N \geq 2\) the linear complexity profile \(L(a,N)\) at \(N\) of a sequence \(a = a_0, a_1,\dots\) over a commutative ring \(R\) with \(1\) is the least \(L\) such that there are constants \(c_1, \dots, c_L \in R\) satisfying \(-a_i = c_1a_{i-1}+c_2a_{i-2}+\dots+c_La_{i-L}\) for all \(L \leq i \leq N-1\), with the convention that \(L(a,N) = N\) if such constants do not exist, and \(L(a,N) = 0\) if \(a_j = 0\), \(j = 0,1,\dots N-1\). The linear complexity of \(a\) is defined by \(L(a) = \sup_{N\geq 2}L(a,N)\).
Let \(q = p^r\) for a prime \(p\), let \(\mathbb F_q\) be the finite field of order \(q\) and suppose that \(\{\beta_0,\beta_1,\dots,\beta_{r-1}\}\) is a basis of \(\mathbb F_q\) over \(\mathbb F_p\). Then with \(\xi_i = i_0\beta_0+i_1\beta_1+\dots+i_{r-1}\beta_{r-1}\) if \(i = i_0+i_1p+\dots+i_{r-1}p^{r-1}\) is the \(p\)-adic representation of \(i = 0,1,\dots,q-1\), we obtain an ordering of the elements of \(\mathbb F_q\).
For a primitive element \(\gamma\) of \(\mathbb F_q\) and a divisor \(d > 1\) of \(q-1\) let \(S\) be a sequence over the residue class ring \(\mathbb Z_d\) satisfying \(s_i = \text{ ind}_\gamma(\xi_i)\) modulo \(d\), \(1 \leq i \leq q-1\), where \(\text{ ind}_\gamma(\xi)\) denotes the discrete logarithm to the base \(\gamma\). The author shows that \(S\) satisfies \(L(S,N) > N^{1/2}/(4p^{1/2}q^{1/4})\) for \(2 \leq N \leq q\), and \(L(S) > q^{1/4}/4\). The result improves earlier results of W. Meidl and A. Winterhof [IEEE Trans. Inform. Theory 47, 2807–2811 (2001; Zbl 1032.94004)]. Exact results on the linear complexity for the special case where \(r = 1\), i.e. \(\mathbb F_q\) is a prime field, and \(d\) is prime can be found in [C. Ding and T. Helleseth, Inform. Process. Lett. 66, 21–25 (1998)].
For the entire collection see [Zbl 1047.94002].


11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11T24 Other character sums and Gauss sums
11Y16 Number-theoretic algorithms; complexity
68Q25 Analysis of algorithms and problem complexity
94A60 Cryptography


Zbl 1032.94004