Families of sequences with good family complexity and cross-correlation measure

Pseudorandom sequence is a sequence of numbers generated deterministically and looks random. It is called binary ($k$-ary or $k$-symbol) sequence if its elements are in {-1,+1} (resp. $\{a_{1},a_{2},\ldots,a_{k}\}$ for some numbers $a_{i}$). Pseudorandom sequences have a lot of application areas such as telecommunication, cryptography, simulation see for example [8, 12, 34, 39]. According to its application area, the quality of a pseudorandom sequence is evaluated in many directions. There are statistical test packages (for example L’Ecuyer’s TESTU01 [19], Marsaglia’s Diehard [25] or the NIST battery [35]) for evaluating the quality of a pseudorandom sequence. In addition to that, there are proven theoretical results on some randomness measures that a pseudorandom sequence needs to satisfy. For instance, linear complexity, (auto)correlation, discrepancy, well-distribution and others, see [16, 39] and references therein. In some cases one needs many pseudorandom binary sequences, for instance in cryptographic applications. Therefore, their randomness has to be proven by several figures of merit, e.g. family complexity, cross-correlation, collision, distance minimum, avalanche effect and others, see [37] and references therein. The typical values of some randomness measures of a truly random sequence are proven in [3, 5, 32]. Sequences satisfying typical values are so called good sequences.

After Mauduit and Sárközy [27] introduced a construction method of good binary sequences by using Legendre symbol, other construction methods have been given in the literature [6, 7, 21]. In 2004, Goubin, Mauduit and Sárközy [14] first constructed large families of pseudorandom binary sequences. Later, many new constructions [10, 15, 20, 26, 29, 30] and their complexity bounds [31, 33, 36] were developed, see [37] for others.

These pseudorandom measures defined for binary sequences have been extended to sequences of $k$-symbols [11, 28, 40] and some constructions of good $k$-symbols sequences were given in [2, 9, 13, 22, 24].

Huaning Liu and Xi Liu [23] constructed new family of binary sequences has both small cross-correlation measure and large family complexity.

In this paper we study two such measures the family complexity (in short $f$-complexity) and the cross-correlation measure of order $\ell$ of families of binary and $k$-ary sequences.

Ahlswede et al. [1] introduced the $f$-complexity as follows.

We have the trivial upper bound

where $|{\mathcal{F}}|=F$ denotes the size of the family ${\mathcal{F}}$.

Gyarmati et al. [17] introduced the cross-correlation measure of order $\ell$.

For a family ${\mathcal{F}}$ of binary sequences of length $N$ with $|{\mathcal{F}}|<2^{N/12}$, the expected value of the cross-correlation measure of order $\ell\leq N/(6\log_{2}|{\mathcal{F}}|)$ is $\Phi_{\ell}({\mathcal{F}})\approx\left(N\log\left(\begin{array}[]{c}N\\ \ell\end{array}\right)+\ell\log{|{\mathcal{F}}|}\right)^{1/2}$, see [32].

We use the notation $\Phi^{\circ}_{\ell}$ for the cross correlation $\Phi_{\ell}$ evaluated for fixed $M=F$ and $d_{i}=0$ for all $i\in\{1,2,\ldots,l\}$.

Winterhof and the author in [43] proved the estimation of the $f$-complexity $C({\mathcal{F}})$ of a family ${\mathcal{F}}$ of binary sequences

in terms of the cross-correlation measure $\Phi_{\ell}(\overline{{\mathcal{F}}}),\ell\in\{1,2,\ldots,\log_{2}{F}\}$ of the dual family $\overline{{\mathcal{F}}}$ of binary sequences

as follows

In Section II we generalize the construction of the family of binary pseudorandom sequences presented in [43]. We prove a bound on the $f$-complexity of the family of binary sequences of Legendre-symbols of irreducible polynomials $f_{i}(x)=x^{d}+a_{2}i^{2}x^{d-2}+a_{3}i^{3}x^{d-3}+\cdots+a_{d-2}i^{d-2}x^{2}+a_{d}i^{d}$ defined as

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.

In Section III we study another family of binary sequences

for a positive integer $d$. We prove that ${\mathcal{F}}_{2}$ has high $f$-complexity and low cross-correlation measure by using (2). We note that the roots of an irreducible polynomial are called to be conjugate to each other.

In Section IV we extend the relation (2) to the family of sequences on $k$-symbols alphabet. Finally, we show in Section V that extension of the family ${\mathcal{F}}_{2}$ to $k$-symbols alphabet has also high $f$-complexity and low cross-correlation measure.

Throughout the paper, the notations $U\ll V$ and $U=O(V)$ are equivalent to the statement that $|U|\leq cV$ holds with some positive constant $c$. Moreover, the notation $f(n)=o(1)$ is equivalent to $\lim_{n\to\infty}{f(n)}=0.$

In this section we present an extension of the family of sequences given in [43], where a family of sequences of Legendre symbols with irreducible quadratic polynomials and its dual family were given. It was shown that both families have high family complexity and small cross-correlation measure up to a large order $\ell$. Namely, for $p>2$ a prime and $b$ a quadratic nonresidue modulo $p$ they study the following family ${\mathcal{F}}$ and its dual family $\overline{{\mathcal{F}}}$:

and they show

for each integer $k=1,2,\ldots$ Then (2) immediately implies

We now present an extension of this result to higher degree polynomials over prime finite fields. Note that for these families we also get analog bounds for their duals.

Let $p>2$ be a prime number, $d\geq 5$ and $\Omega_{p,d}$ be a set of irreducible polynomials over ${\mathbb{F}}_{p}$ of degree $d$ defined as

According to Definition 2 we need to estimate

We will first show that

is a monic square-free polynomial and then apply Weil’s Theorem, see [18, 38, 42]. Since each $f_{i_{j}},\ j=1,2,\ldots,k$ is an irreducible polynomial it is enough to show that they are distinct from each other. Assume that $f_{i_{j}}(X+d_{j})=f_{i_{\ell}}(X+d_{\ell})$ for some $j,\ell=1,2,\ldots,k$. Then by comparing the coefficients of the term $X^{d-1}$ we have $d_{j}=d_{\ell}$ since $p\nmid d$. Hence we have the equality $f_{i_{j}}(X)=f_{i_{\ell}}(X)$. But then by comparing the coefficients of the terms $X^{d-2}$ and $X^{d-3}$ we have

Since $a_{2}$ and $a_{3}$ are non zero we have

This implies that $i_{j}=i_{\ell}$, a contradiction. Therefore $h$ is a square-free polynomial. Since the degree of $h(x)$ is $dk$ then the following holds

Similarly we can show that

for $k\in\{1,2,\ldots,p-1\}$. Next we use (2) to get the bounds on the family complexity.

$\Box$

We note that each two sequences in ${\mathcal{F}}_{f}$ (resp. $\overline{{\mathcal{F}}_{f}}$) given in Theorem 1 are distinct as $\Phi_{2}({{\mathcal{F}}_{f}})<p$ (resp. $\Phi_{2}(\overline{{\mathcal{F}}_{f}})<p$). Hence, we have the family size $|{\mathcal{F}}_{f}|=p$ for the family. In the next result, we give an upper bound on the number $\#\{{\mathcal{F}}_{f}|f\in\Omega_{p,n}\}$ of distinct families. This result is a direct consequence from the paper [4]. Before that we will give some notation. Let $C_{\alpha}:x(y^{p}+y)=\alpha(x^{2}+1)$ be curves over $\mathbb{F}_{p}$ for $\alpha\in\mathbb{F}_{p}^{\times}$. Let $\#C_{\alpha}(\mathbb{F}_{p^{n}})$ denote the number of points $(x,y)\in{\mathbb{F}}_{p^{n}}$ on $C_{\alpha}$ and define $S_{\alpha}(\mathbb{F}_{p^{n}}):=\#C_{\alpha}(\mathbb{F}_{p^{n}})-(p^{n}+1)$. Let $\mu$ denote the Möbius function and $[p\text{ divides }n]$ denote its truth value, i.e., $[p\text{ divides }n]:=1$ if $p\text{ divides }n$, and $[p\text{ divides }n]:=0$ otherwise.

Now we construct a larger family with both small cross-correlation measure and high $f$-complexity. However, for these families of sequences we cannot say anything about their duals.

Next, we prove the bound on family complexity by using (2) with $\Phi^{\circ}_{k}$ instead $\Phi_{k}$. Because estimating $\Phi^{\circ}_{k}$ is easier in this case. In order to calculate $\Phi^{\circ}_{k}(\overline{{\mathcal{F}}})$ we need to estimate

Note that $f(X)\in\Omega_{d}$ if and only if $f(X)=(X-\beta)(X-\beta^{p})\cdots(X-\beta^{p^{d-1}})$ for some $\beta\in{\mathbb{F}}_{p^{d}}$ with ${\rm Tr}(\beta)=0$ and $\beta\not\in{\mathbb{F}}_{p^{t}}$ for any $t\mid d,t<d$. Hence we rewrite $V$ as

where $N$ is the norm function from ${\mathbb{F}}_{p^{d}}$ to ${\mathbb{F}}_{p}$. We note that $\chi(\alpha)=\left(\frac{N(\alpha)}{p}\right)$ is the quadratic character of ${\mathbb{F}}_{p^{d}}$ and the number of elements $\alpha\in{\mathbb{F}}_{p^{t}},\ t\mid d$ and $t<d$ but $\alpha\not\in{\mathbb{F}}_{p^{d}}$ is at most

Thus we can estimate $V$ as follows:

The last inequality follows by Weil’s Theorem [41]. By (1) $2^{C({\mathcal{F}})}\leq|{\mathcal{F}}|=F$ and since $k=C({\mathcal{F}})$ we get $k\leq log_{2}{F}$. Therefore by using (2) we have

$\Box$

Gyarmati et. al. proved that the cross-correlation measure of the family given in Theorem 2 is small and satisfies

for each integer $k\in\{1,2,3,\ldots,p-1\}$, see [17, Theorem 8.14].

In [28] the correlation measure of a sequence consisting of symbols $\{a_{1},a_{2},\ldots,a_{k}\}$ is defined. We similarly extend the definition of cross-correlation measure for a family of sequences consisting of $k$-symbols in the following.

The definition of $f$-complexity C(${\mathcal{F}}$) for a family ${\mathcal{F}}$ of binary sequences can be directly generalized to a family of sequences consisting of $k$-symbols.

Now we prove the following extension of (2).