Families of sequences with good family complexity and cross-correlation measure
This work addresses the need for robust pseudorandom sequences in cryptography and coding theory, but it is incremental as it generalizes known methods to broader alphabets.
The paper tackles the problem of constructing families of pseudorandom sequences with high family complexity and low cross-correlation, extending results from binary to k-ary alphabets. It proves bounds for specific families, such as those based on Legendre symbols, showing they achieve large complexity and small cross-correlation up to high orders.
In this paper we study pseudorandomness of a family of sequences in terms of two measures, the family complexity ($f$-complexity) and the cross-correlation measure of order $\ell$. We consider sequences not only on binary alphabet but also on $k$-symbols ($k$-ary) alphabet. We first generalize some known methods on construction of the family of binary pseudorandom sequences. We prove a bound on the $f$-complexity of a large family of binary sequences of Legendre-symbols of certain irreducible polynomials. We show that this family as well as its dual family have both a large family complexity and a small cross-correlation measure up to a rather large order. Next, we present another family of binary sequences having high $f$-complexity and low cross-correlation measure. Then we extend the results to the family of sequences on $k$-symbols alphabet.