Sequences with almost perfect linear complexity profiles and curves over finite fields

Abstract

For stream ciphers, we need to generate pseudorandom sequences which are of properties of unpredictability and randomness. A important measure of unpredictability and randomness is the linear complexity profile (l.c.p.) l a(n) of a sequence a. A sequence a is called almost perfect if the l.c.p. is l a(n) = n/2+O(1). Based on curves over finite fields, we present in this correspondence a method to construct almost perfect sequences. We also illustrate our construction by explicit examples from the projective line and elliptic curves over the binary field.