## 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].

### MSC:

 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