Constructions of sequences with almost perfect linear complexity profile from curves over finite fields (Q1964068)

Let \(\mathbb{F}_q\) denote the finite field with \(q\) elements. The linear complexity of a sequence \(a_1,a_2,\dots,a_n\) of elements from \(\mathbb{F}_q\) is the least \(k\) such that the sequence is a \(k\)th-order shift-register sequence. This notion is important in the theory of stream ciphers. Given an infinite sequence \({\mathbf a}=a_1,a_2,\dots\) of elements from \(\mathbb{F}_q\), let \(l(n)\) denote the linear complexity of \(a_1,a_2,\dots,a_n\). Then the sequence of integers \(\{l(n)\}\) is called the linear complexity profile of \textbf{a}. The sequence \textbf{a} is said to have a \(d\)-almost perfect linear complexity profile if \[ {{n+1-d}\over 2}\leq l(n)\leq {{n+d}\over 2} \] for all \(n\geq 1\). In this paper, the authors generalize a construction given by the first and the third authors [IEEE Trans. Inf. Theory 45, 1267-1270 (1999; Zbl 0943.94013)] that uses the coefficients in the local expansion of a rational function \(f\) at a rational point \(P\) on a curve defined over \(\mathbb{F}_q\) to form a \(d\)-almost perfect sequence, where \(d\) depends on the degree of \(f\) and the order of \(f\) at \(P\). To perform the construction, one needs a local parameter \(t\) at \(P\) such that the divisor of \(t\) is \(P+Q-D\), where \(D\) is a positive divisor of degree two. Thus, the construction requires a hyperelliptic (or rational or elliptic) curve. The authors give some examples using the projective line and an elliptic curve over \(\mathbb{F}_3\).