# zbMATH — the first resource for mathematics

Constructions of sequences with almost perfect linear complexity profile from curves over finite fields. (English) Zbl 0943.94005
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 a. The sequence 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$$.

##### MSC:
 94A55 Shift register sequences and sequences over finite alphabets in information and communication theory 11T71 Algebraic coding theory; cryptography (number-theoretic aspects) 14G15 Finite ground fields in algebraic geometry 65C10 Random number generation in numerical analysis
Full Text: