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

1.   Introduction

Pseudorandom sequence is a sequence of numbers generated deterministically and looks random. It is called a 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 wide array of application areas, including telecommunication, cryptography, simulation, numerical integration, spread-spectrum communications, and randomized algorithms, among others ^[8,12,34,39]. In telecommunication, pseudorandom sequences are essential for tasks such as channel coding, error detection and correction, and synchronization in spread-spectrum and CDMA systems. In cryptography, they underpin the generation of secure keys, stream ciphers, and various cryptographic protocols, ensuring data confidentiality and integrity. Simulation applications, particularly in Monte Carlo methods, rely on pseudorandom sequences to model and analyze complex systems and stochastic processes with high accuracy.

According to their application area, the quality of a pseudorandom sequence is evaluated in multiple dimensions. There are several statistical test packages available for assessing the quality of pseudorandom sequences, such as L'Ecuyer's TESTU01 ^[20], Marsaglia's Diehard ^[25], and the NIST Statistical Test Suite ^[35]. These tools perform a battery of tests to evaluate properties like uniform distribution, independence, and absence of detectable patterns. In addition to empirical testing, there are established theoretical results concerning various randomness measures that a pseudorandom sequence must satisfy. These measures include linear complexity, which assesses the sequence's resistance to linear attacks; (auto)correlation, which evaluates the sequence's suitability for synchronization and multiple access; discrepancy, which measures the uniformity of distribution in multi-dimensional spaces; and well-distribution, which ensures that the sequence covers the space evenly ^[17,39].

In certain applications, particularly in cryptography, there is a need to generate multiple pseudo-random binary sequences simultaneously. This requirement requires that the sequences maintain high levels of randomness in several metrics to prevent vulnerabilities. Therefore, their randomness must be validated using multiple figures of merit, such as family complexity, which measures the difficulty of distinguishing any single sequence from others in the family; cross-correlation, which assesses the independence between different sequences; collision resistance, which ensures that sequences do not inadvertently produce the same output; minimum distance, which evaluates the separation between sequences in the family; and the avalanche effect, which ensures that small changes in input lead to significant changes in output ^[37]. These measures collectively enhance the robustness and security of cryptographic systems by ensuring that the pseudorandom sequences are sufficiently unpredictable and resilient against various attack vectors.

Furthermore, pseudorandom sequences are integral to numerical integration techniques, particularly in quasi-Monte Carlo methods, where low-discrepancy sequences improve the convergence rate compared to purely random sequences ^[32]. In randomized algorithms, pseudorandomness ensures that algorithms perform efficiently on average, providing reliable performance across diverse problem instances. Additionally, in error correction and detection schemes, pseudorandom sequences facilitate encoding and decoding processes by introducing controlled randomness that helps to identify and correct errors.

The typical values of certain randomness measures for truly random sequences have been established in foundational works ^[3,5,32], offering benchmarks to evaluate the adequacy of pseudorandom sequences in specific applications. Sequences that meet these typical values are termed good sequences. Following Mauduit and Sárközy's work ^[27], which introduced a method to construct good binary sequences using the Legendre symbol, other construction methods have been developed, enriching the literature with various techniques ^[6,7,21].

In 2004, Goubin, Mauduit, and Sárközy ^[14] pioneered the construction of large families of pseudo-random binary sequences. Subsequent research expanded upon this, leading to various new constructions ^{[10,15,26,29,30]} and complexity bounds ^[31,33,36], with further developments documented in ^[37]. The measures of pseudorandomness originally defined for binary sequences have also been generalized to sequences over $k$-symbol alphabets ^[11,28,40], and constructions of good sequences for $k$-symbol alphabets have been proposed ^{[2,9,13,22,24]}.

Recently, Huaning Liu and Xi Liu ^[23] constructed a new family of binary sequences with both a low cross-correlation measure and high family complexity. In this paper, we investigate the family complexity (abbreviated as $f$-complexity) and the cross-correlation measure of order $\ell$ for families of binary and $k$-ary sequences, considering not only binary alphabets but also sequences over $k$-symbol (or $k$-ary) alphabets.

We begin by presenting established definitions in this section to facilitate a clear introduction of our results. Ahlswede et al. ^[1] defined the $f$-complexity as follows.

Definition 1. The $f$-complexity $C({\mathcal F})$ of a family ${\mathcal F}$ of binary sequences $E_N \in \{-1, +1\}^N$ of length $N$ is the greatest integer $j \geq 0$ such that for any $1 \leq i_1 < i_2 < \cdots < i_j \leq N$ and any $\epsilon_1, \epsilon_2, \ldots, \epsilon_j \in \{-1, +1\}$, there is a sequence $E_N = (e_1, e_2, \ldots, e_N)\in {\mathcal F}$ with

We have the trivial upper bound

where $| {\mathcal F}| = F$ denotes the size of the family ${\mathcal F}$. Gyarmati et al. ^[18] introduced the cross-correlation measure of order $\ell$.

Definition 2. The cross-correlation measure of order $\ell$ of a family ${\mathcal F}$ of binary sequences

is defined as

where $D$ denotes an $\ell$ tuple $(d_1, d_2, \ldots, d_\ell)$ of integers such that $0 \leq d_1 \leq d_2 \leq \cdots \leq d_\ell < M+d_\ell \leq N$ and $d_i \neq d_j$ if $E_{i, N} = E_{j, N}$ for $i \neq j$, and $I$ denotes an $\ell$ tuple $(i_1, i_2, \ldots, i_\ell)\in\{1, 2, \ldots, F\}^\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

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 third 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:

Contribution and Outline. In Section 2, we generalize the construction of a family of binary pseudorandom sequences presented in ^[43]. We establish a bound on the $f$-complexity of a family of binary sequences generated from the Legendre symbols of irreducible polynomials of the form

for an odd prime number $p$, defined as

We demonstrate that both this family and its dual family exhibit a high family complexity and a low cross-correlation measure up to a large order. Unlike the results in ^[43], we show that the cross-correlation measure of this family increases and the lower bound on family complexity decreases as the degree $d$ increases (see Theorem 1).

In Section 3, we analyze a different family of binary sequences

for a positive integer $d \leq \sqrt{p}/2$. We prove that ${\mathcal F}_2$ has high $f$-complexity and a low cross-correlation measure based on (1.3). We observe that, similar to ${\mathcal F}_1$, these measures weaken as $d$ increases. On the other hand, the family size of ${\mathcal F}_2$ is larger, on the order of $p^{d-2}$ (see Theorem 2), which is also achieved by a different construction in ^[23].

In Section 4, we extend the relation (1.3) to families of sequences over a $k$-symbol alphabet. Finally, in Section 5, we demonstrate that an extension of the family ${\mathcal F}_2$ to a $k$-symbol alphabet also maintains high $f$-complexity and a low cross-correlation measure.

Throughout this paper, the notations $U \ll V$ and $U = O(V)$ indicate that $\vert U \vert \leq cV$ for some positive constant $c$. Additionally, $f(n) = o(1)$ denotes that $\lim_{n \to \infty} f(n) = 0$.

2.   A family and its dual with bounded cross-correlation and family complexity measures

We note that there are several related constructions of families of binary sequences defined with the Legendre symbol and polynomials; see ^[16,18,43]. In this section we present similar families of sequences as 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 measures 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$ and the dual of a family is defined as in (1.2). Then (1.3) immediately implies

We now present a generalization of this result to higher degree polynomials over prime finite fields. Note that for these families we also obtain 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

Theorem 1. Let ${\mathcal F}_f$ be a family of binary sequences for some $f \in \Omega_{p, d}$ defined as

where $f_i(X) = i^df(X/i)$ for $i \in \{1, 2, \ldots, p-1 \}$ and $d < p^{1/2}/2$. Let $\overline{ {\mathcal F}_f}$ be the dual of ${\mathcal F}_f$. Then we have

for each integer $k \in \{1, 2, \ldots, p-1\}$ and

and

If $d = p^ \varepsilon$, then we obtain the lower bound $\left(\frac{1}{2}-\varepsilon-o(1)\right) \frac{\log p}{\log 2}$. In particular, the bound becomes trivial for $\varepsilon \geq 1/2$.

Proof. Since otherwise the cross-correlation values, bounded by $p-1$ the length of the sequences, become greater than $p$, we may assume $d < p^{1/2}/2$. We note that $f(X, i) : = f_i(X)$ is an homogeneous polynomial of degree $d$. Thus, it is enough to choose an irreducible polynomial

such that $a_2, a_3\not\equiv 0\ (\mbox{mod}\ p)$. It is clear that each $f_i$ is irreducible for $i \in \{1, 2, \ldots p-1\}$ whenever $f(X)$ is irreducible.

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 ^[19,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 (1.3) to obtain the bounds on the family complexity.

□

Remark 1. We note that the results in Theorem 1 become weaker with increasing degree, but the size of the family stays the same. The family complexity of a 'good' family of sequences is expected to be roughly of the order of magnitude $\log(F)$, where $F$ is the size of the family. Note that the family ${\mathcal F}_f$ constructed in Theorem 1 has the family complexity lower bounded by $\frac{\log({\mathcal F}_f)}{2\, \log\, 2}$ for small $d$ where $| {\mathcal F}_f| = p-1$. Thus, ${\mathcal F}_f$ would be a good family of sequence if $C({ {\mathcal F}_f})$ is upper bounded similarly and this lower bound is improved.

Example 1. Let $d = 5$ and $p = 11$. The polynomial $f = x^5 + x^3 + 2x^2 + 3$ is in the set $\Omega_{11, 5}$. The irreducible polynomials generated by $f_i(X) = i^5 f(X/i)$ for $i \in \{1, 2, \ldots, 10 \}$ are $f_1(x) = x^5 + x^3 + 2x^2 + 3$, $f_2(x) = x^5 + 4x^3 + 5x^2 + 8$, $f_3(x) = x^5 + 9x^3 + 10x^2 + 3$, $f_4(x) = x^5 + 5x^3 + 7x^2 + 3$, $f_5(x) = x^5 + 3x^3 + 8x^2 + 3$, $f_6(x) = x^5 + 3x^3 + 3x^2 + 8$, $f_7(x) = x^5 + 5x^3 + 4x^2 + 8$, $f_8(x) = x^5 + 9x^3 + x^2 + 8$, $f_9(x) = x^5 + 4x^3 + 6x^2 + 3$, $f_{10}(x) = x^5 + x^3 + 9x^2 + 8$. The sequences generated by these polynomials are

This sequence family does not have the complexity 3, since the tuples $\{[1,1,1]$, $[1,1,-1]$, $[1,-1,1]$, $[1,-1,-1]$, $[-1,1,1]$, $[-1,1,-1]$, $[-1,-1,1]$, $[-1,-1,-1]\}$ in the vector space $\mathbb F_{2}^3$ are not in the all possible 3 tuples of the sequence family. For example, the first three bits of sequence family are $[[-1,-1,1],$ $[-1,1,-1],$ $[1,1,-1],$ $[1,1,1],$ $[1,1,1],$ $[1,-1,-1],$ $[-1,-1,1],$ $[-1,-1,-1],$ $[1,1,1],$ $[-1,-1,-1]]$. However, this multi-list does not contain all the vectors in $\mathbb F_{2}^3$. On the other hand, its family complexity is 2. The cross-correlation measure of order 5 of the family gets the maximum value of 10 with M = 10, I = [2,6,7,8,10] and D = [0,0,0,0,0]. The dual family $\overline{ {\mathcal F}_f}$ gets the cross-correlation measure 9 of order 5 with I = [3,4,6,9,10] and D = [0,0,0,1,1]. The complexity of the dual family is 1. We note that the right-hand side of (2.1) is approximately 75, and so it is far from being close for small primes $p$. But, as it is an asymptotic bound, it requires computations for large primes. On the other hand, the lower bound in (2.2) and (2.2) is $-\frac{1}{2}$, and so it is seen that the family complexities in this example are very close to this bound. Similarly, we note that this bound holds for large primes $p$.

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-1$ for the family. In the next result, we give an upper bound on the number $\#\{ {\mathcal F}_f \vert 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.

Corollary 1.

where

Proof. The family ${\mathcal F}$ is constructed by using irreducible polynomials $f \in \Omega_{p, n}$. By [4, Theorem 1], we obtain the number of irreducible polynomials in terms of $F_p(n)$. Then, [4, Theorem 5] gives the result. □

3.   A large family of sequences with low cross-correlation and high family complexity

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

Theorem 2. Let $p > 2$ be a prime number, $d \in {\mathbb Z}^+$ and $p \nmid d$. Let $\Omega_d$ be the set defined as

Let a family ${\mathcal F}_d$ of binary sequences be defined as

Then,

The family size equals

for $3 \leq d < p^{1/2}/2$.

Proof. It is clear by the Weil bound that each irreducible polynomial generates a distinct sequence in ${\mathcal F}$. Yucas ^[44] proved that the number of irreducible polynomials over ${\mathbb{F}}_p$ of degree $d$ with $p \nmid d$ and trace nonzero equals

By doing calculations, we obtain

With the smallest $p = 3$, we see that

Hence,

and we have proved the size of family.

Next, we prove the bound on family complexity by using (1.3) 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

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 given in (3.2),

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.1), $2^{C({\mathcal F})} \leq | {\mathcal F}| = F$ and since $k = C({\mathcal F})$ we obtain $k\leq \log_2{F}$. Therefore, by using (1.3) we have

□

We note that the lower bound in Theorem 2 on $C({\mathcal F}_d)$ increases when $d$ increases. In particular, it reduces to $\left(\frac{1}{2}-o(1)\right) \frac{\log p}{\log 2}$ if $d = 3$.

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 [18, Theorem 8.14].

Example 2. Let $p = 11$ and $d = 5$.

This family consists of 2640 irreducible polynomials. The f-complexity of this family is 8. The lower bound in (3.1) is approximately 3, which is convenient with this example. However, the lower bound is not close for small primes. On the other hand, the cross-correlation measure of order 5 of the family gets the maximum value 10 with M = 10, I = [2573,244,2118,1629,740] and D = [0,0,0,0,0]. This value is also far from the asymptotic bound in (3.3).

4.   Sequences on $k$-symbols alphabet

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.

Definition 3. The cross-correlation measure of order $\ell$ of a family ${\mathcal F}$ of sequences $E_{i, N} = (e_{i, 1}, e_{i, 2}, \ldots, e_{i, N}) \in \{a_1, a_2, \ldots, a_k\}^N$, $i = 1, 2, \ldots, F$, is defined as

for

where $W \in \{a_1, a_2, \ldots, a_k\}^\ell$, $D$ denotes an $\ell$ tuple $(d_1, d_2, \ldots, d_\ell)$ of integers such that $0 \leq d_1 \leq d_2 \leq \cdots \leq d_\ell < M+d_\ell \leq N$ and $d_i \neq d_j$ if $E_{i, N} = E_{j, N}$ for $i \neq j$, and $I$ denotes an $\ell$ tuple $(i_1, i_2, \ldots, i_\ell)\in\{1, 2, \ldots, F\}^\ell$.

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.

Definition 4. The $f$-complexity $C({\mathcal F})$ of a family ${\mathcal F}$ of $k$-symbol sequences $E_N \in \{a_1, a_2, \ldots, a_k\}^N$ of length $N$ is the greatest integer $j \geq 0$ such that for any $1 \leq i_1 < i_2 < \cdots < i_j \leq N$ and any $\epsilon_1, \epsilon_2, \ldots, \epsilon_j \in \{a_1, a_2, \ldots, a_k\}$ there is a sequence $E_N = (e_1, e_2, \ldots, e_N)\in {\mathcal F}$ with

Now we prove the following extension of (1.3).

Theorem 3. Let ${\mathcal F}$ be a family of sequences $(e_{i, 1}, \ldots, e_{i, N}) \in \{a_1, a_2, \ldots, a_k\}^N$ for $i = 1, 2, \ldots, F$ and $\overline{ {\mathcal F}}$ its dual family of binary sequences $(e_{1, n}, e_{2, n}, \ldots, e_{F, n}) \in \{a_1, a_2, \ldots, a_k\}^{F}$ for $n = 1, 2, \ldots, N$. Then we have

and

where $\log_k$ denotes the base $k$ logarithm.

Proof. Assume that for an integer $j$ a specification

for $B = (b_1, b_2, \ldots, b_j) \in \{a_1, a_2, \ldots, a_k\}^j$ occurs in the family ${\mathcal F}$ for some $k \in \{1, 2, \ldots, F\}$. Let $A$ denotes the number of sequences in ${\mathcal F}$ satisfying (4.3). By the definition of cross-correlation, we have

Hence, we obtain that

If $j < \log_k{F} - \log_k{\gamma_j(\overline{ {\mathcal F}})}$ then there exists at least one sequence in ${\mathcal F}$ satisfying (4.3). Therefore, for all integers $j \geq 0$ satisfying

we have $A > 0$ which completes the proof of (4.1). And the proof of (4.2) is done similarly. □

5.   A large family of $k$-symbols sequences with low cross-correlation and high family complexity

In this section we extend the family of binary sequences that we have presented in Section 3 to the $k$-symbol alphabet. We prove the following generalization of Theorem 2. The proof is similar to proof of Theorem 2 see also [27, Theorem 3].

Theorem 4. Let $d$ and $p > 2$ be distinct prime numbers and $k$ be a positive integer such that

Let $f_\beta$ be an irreducible polynomial of degree $d$ over the finite field ${\mathbb{F}}_p$ such that

for an element $\beta \in {\mathbb{F}}_{p^d}$. Let a family ${\mathcal F}$ of $k$-ary sequences be defined as

for some character $\chi$ of order $k$. Then we have

for each integer $l \in \{2, 3, \ldots, p-1\}$ and

The family size equals

Proof. Let $a$ be a $k$-th root of unity and $S(a, m)$ denote

Then we have

Now we estimate $g({\mathcal F}, W, M, D, I)$ as follows:

Now consider the polynomial

We will show that it is not a $k$-th power of a polynomial over ${\mathbb{F}}_p$. As $n+d_j < p$ for $j = 1, 2, \ldots, \ell$, we can write $f$ as follows:

for some $\beta_{i_1}, \ldots, \beta_{i_\ell} \in {\mathbb{F}}_{p^d} \backslash {\mathbb{F}}_p$ and ${{\rm{Tr}}}(\beta_{i_j}) = 0$ for all $j \in \{1, 2, \ldots, \ell\}$. Then, the linear terms $(n+d_1-\beta_{i_1}), \ldots, (n+d_\ell-\beta_{i_\ell})$ are distinct from each other. So it is enough to show that the power of each component is not divisible by $k$. And this holds as we have $t_1, \ldots, t_\ell < k$ and $\gcd(k, \frac{p^d-1}{p-1}) = 1$.

By applying Weil's Theorem to the inner character sum, we obtain

and by substituting this into Definition 3 we complete the proof of (5.1).

Next we prove the bound (5.2). Before this we note that family size equals the number of irreducible polynomials of degree $d$ over ${\mathbb{F}}_p$ having zero trace since they all produce a distinct sequence in ${\mathcal F}$. Note that there are $\frac{p^d-p}{p}$ distinct elements in ${\mathbb{F}}_{p^d} \backslash {\mathbb{F}}_p$ having zero trace, and $d$ of them combines into an irreducible polynomial over ${\mathbb{F}}_p$. So we have

Now we estimate

Similar to the proof of (5.1), we have a similar equation array as given in (5.4).

Since ${{\rm{Tr}}}(\beta) = 0$ and $\gcd(k, \frac{p^d-1}{p-1}) = 1$, the polynomial inside the character sum is not a $k$-th power. Thus, by Weil's Theorem, we have

and so by Definition 3 we have

Therefore, by using (5.3) and (5.5), we obtain that

as desired. □

6.   Conclusions

Pseudorandom sequences are used in many practical areas, and their quality is decided by statistical test packages as well as by proved results on certain measures. In addition, a large family of good pseudorandom sequences in terms of several directions is required in some applications. In this paper we studied two such measures: the $f$-complexity, and the cross-correlation measure of order $\ell$ for family of sequences on binary and $k$-symbols alphabets. We considered two families of binary sequences of Legendre-symbols

for irreducible polynomials $f_i(x) = x^d + a_2i^2x^{d-2} + a_3i^{3}x^{d-3} + \cdots + a_{d-2}i^{d-2}x^{2} + a_di^d$ and

for a positive integer $d$. We showed that the families ${\mathcal F}_1$ and ${\mathcal F}_2$ have both a large family complexity and a small cross-correlation measure up to a rather large order. Then we proved the analog results for the family of sequences on $k$-symbols alphabet, and constructed a good family of $k$-symbols sequences.

Author contributions

All authors contributed equally to all parts of the paper. All authors have read and approved the final version of the manuscript for publication.

Use of Generative-AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgement

The authors would like to thank anonymous reviewers for their careful reading and helpful suggestions, which improved the presentation of the paper.

Conflict of interest

The authors declare that there is no conflict of interest.