Abstract
We study the relationship between two measures of pseudorandomness for families of binary sequences: family complexity and cross-correlation measure introduced by Ahlswede et al. in 2003 and recently by Gyarmati et al., respectively. More precisely, we estimate the family complexity of a family \((e_{i,1},\ldots ,e_{i,N})\in \{-1,+1\}^N\), \(i=1,\ldots ,F\), of binary sequences of length \(N\) in terms of the cross-correlation measure of its dual family \((e_{1,n},\ldots ,e_{F,n})\in \{-1,+1\}^F\), \(n=1,\ldots ,N\). We apply this result to the family of sequences of Legendre symbols with irreducible quadratic polynomials modulo \(p\) with middle coefficient \(0\), that is, \(e_{i,n}=\big (\frac{n^2-bi^2}{p}\big )_{n=1}^{(p-1)/2}\) for \(i=1,\ldots ,(p-1)/2\), where \(b\) is a quadratic nonresidue modulo \(p\), showing that this family as well as its dual family has both a large family complexity and a small cross-correlation measure up to a rather large order.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Pseudorandom binary sequences are used in many areas such as telecommunication, cryptography, simulation, spectroscopy, see for example [2, 7, 11]. The quality of a pseudorandom sequence has to be screened by statistical test packages (for example, L’Ecuyer’s TESTU01, Marsaglia’s Diehard or the NIST battery) as well as by proving theoretical results on certain measures of pseudorandomness such as the correlation measure of order \(\ell \) introduced by Mauduit and Sárközy [9]. Here we focus on theoretical results.
In many applications such as cryptography, one needs a large family of good pseudorandom sequences and has to prove bounds on several figures of merit [4, 7]. In this paper we study the relationship of two such quality measures, the family complexity (abbreviated \(f\)-complexity) and the cross-correlation measure of order \(\ell \) of families of binary sequences.
Ahlswede et al. [1] introduced the \(f\)-complexity as follows.
Definition 1.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 \ge 0\) such that for any \(1 \le i_1 < i_2< \cdots < i_j \le 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}|\) denotes the size of the family \({\mathcal F}\).
Gyarmati et al. [4] introduced the cross-correlation measure of order \(\ell \).
Definition 1.2
The cross-correlation measure of order \(\ell \) of a family \({\mathcal F}\) of binary sequences \(E_{i,N} = (e_{i,1},e_{i,2},\ldots , e_{i,N}) \in \{-1+1\}^N\), \(i=1,2, \ldots , F\), is defined as
where \(D\) denotes an \(\ell \) tuple \((d_1,d_2,\ldots , d_\ell )\) of integers such that \(0 \le d_1 \le d_2 \le \cdots \le d_\ell < M+d_\ell \le N\) and \(d_h \ne d_j\) if \(E_{h,N} = E_{j,N}\) for \(h \ne j\), and \(I\) denotes an \(\ell \) tuple \((i_1,i_2, \ldots , i_\ell )\in \{1,2,\ldots ,F\}^\ell \).
In Sect. 2 we estimate the \(f\)-complexity of a family of binary sequences
in terms of the cross-correlation measure of the dual family \(\overline{{\mathcal F}}\) of binary sequences
In Sect. 3 we apply this result to prove a bound on the \(f\)-complexity of the family of sequences of Legendre-symbols of monic quadratic irreducible polynomials with vanishing middle coefficient
where \(b\) is a quadratic non-residue modulo \(p\), showing that this family as well as its dual family has both a large family complexity and a small cross-correlation measure up to a rather large order.
We note that there are several related constructions of families of binary sequences defined with the Legendre symbol and polynomials, see [4, 6] and references therein. For instance, the family given in [6] has a large family complexity but a large cross-correlation measure of order 2. Moreover, the families given in [4] have a small cross-correlation measure, but it is not easy to measure their family complexity; for further details, see the remarks in Sect. 3. One of the aims of this study is to construct a family of binary sequences having both a large family complexity and a small cross-correlation measure.
Throughout the paper, the notation \(U \ll V\) is equivalent to the statement that \(\vert U \vert \le cV\) holds with some positive constant \(c\). Moreover, the notation \(f(n) = o(1)\) is equivalent to
2 A relation between family complexity and cross-correlation measure
In this section we prove the following relationship between the \(f\)-complexity of a family of binary sequences and the cross-correlation measure of its dual family.
Theorem 2.1
Let \({\mathcal F}\) be a family of binary sequences \((e_{k,1},\ldots ,e_{k,N}) \in \{-1,+1\}^N\) for \(k=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 \{-1,+1\}^{F}\) for \(n=1,2,\ldots ,N\). Then we have
where \(\log _2\) denotes the binary logarithm.
Proof
We are looking for the largest \(j\) such that any specification
occurs in the family \({\mathcal F}\) for some \(k \in \{1,2,\ldots ,F\}\). We will prove a sufficient condition for the existence of a sequence in \({\mathcal F}\) satisfying (2) by a counting argument. We know that
Then the number \(A\) of sequences in \({\mathcal F}\) satisfying (2) equals
Extending the product and after easy calculations we have
Thus if
then there exists at least one sequence in \({\mathcal F}\) satisfying (2).
By (1) we may assume \(j \le \log _2F\), and so we get
Therefore for all integers \(j \ge 0\) satisfying
(3) is satisfied and we have \(A > 0\) which completes the proof. \(\square \)
3 A family with low cross-correlation measure and high family complexity
In this section we demonstrate how to apply Theorem 2.1 and prove that the following family of sequences and its dual family have both high family complexity and small cross-correlation measure of order \(\ell \) up to a large order \(\ell \).
Let \(p>2\) be a prime and \(b\) a quadratic nonresidue modulo \(p\). The family \({\mathcal F}\) and its dual family \(\overline{{\mathcal F}}\) are defined as follows:
Since
both families have the same family complexity and cross-correlation measure of order \(\ell \). We will show
for each integer \(\ell =1,2,\ldots \) Then Theorem 2.1 immediately implies
Here we used
which can be verified in the following way. For some \(1\le n_1<n_2\le (p-1)/2\) assume that \(\big (\frac{n_1^2-bi^2}{p}\big )=\big (\frac{n_2^2-bi^2}{p}\big )\) for \(i=1,\ldots ,(p-1)/2\). Since \(i^2\equiv (p-i)^2 \hbox {mod}\, p\) and \(\big (\frac{n_1^2}{p}\big )=\big (\frac{n_2^2}{p}\big )=1\), these Legendre symbols are the same for all \(i=0,\ldots ,p-1\) and thus
by Weil’s bound and we get a contradiction to \(p\ge 11\).
Now we prove (4). According to Definition 1.2 and since the Legendre symbol is multiplicative, we need to estimate sums of the form
where
The result follows from the Weil bound after reducing these incomplete character sums to complete ones using the standard method provided that \(h(X)\) is not a square, see [8, 10, 12]. Since each factor of \(h(X)\) of the form \((X+d)^2-bi^2\) is irreducible over \({\mathbb {F}}_p\), it is enough to show that one factor is distinct from all the others. We may assume that the first factor is of the form \(X^2-bi^2\). Comparing coefficients we see that
is only possible if \(d=0\) and \(i\equiv \pm j \hbox {mod}\, p\). Since \(1\le i,j\le (p-1)/2\) we get \(i=j\) and \(h(X)\) is not a square since either \(d_j\ne d_k\) for \(i\ne k\) or \(d_j=d_k\) and \(i_j\ne i_k\) with \(1\le i_j,i_k\le (p-1)/2\).
Remarks
-
1.
Gyarmati [6] studied the family \({\mathcal F}\) of binary sequences \(E_f = (e_{f,1}, \ldots , e_{f,p}) \in \{-1, +1\}^p\) defined by
$$\begin{aligned} e_{f,n} = \left\{ \begin{array}{ll}\left( \frac{f(n)}{p} \right) &{} \quad \mathrm{if \ }\gcd (f(n),p) =1,\\ \quad 1 &{} \quad \mathrm{if \ }p \mid f(n), \end{array}\right. \end{aligned}$$(5)where \(f\) runs through all non-constant square-free polynomials over \({\mathbb {F}}_p\) of degree at most \(k\). She proved
$$\begin{aligned} C(F) \ge \frac{k}{2\log {2}}\log {p} - O(k \log {(k \log {p})}). \end{aligned}$$However, this family has obviously a very large cross-correlation measure of order 2. (Compare \(E_f\) and \(E_g\) with \(g(X) = f(X+d)\) for some \(d \in {\mathbb {F}}_p^*\).)
-
2.
Gyarmati et al. [3] studied the family \({\mathcal F}\) of sequences \(E_f = (e_{f,1}, \ldots , e_{f,p}) \in \{-1, +1\}^p\) defined by (5) where \(f\) runs through all monic irreducible polynomials of degree d with second leading coefficient 0 and showed in Theorem 8.14 that
$$\begin{aligned} \varPhi _l({\mathcal F}) \ll \ell d p^{1/2}\log {p}. \end{aligned}$$We note that for \(d=2\) the polynomials \(f\) are of the form \(X^2 - a\) where \(a\) is a quadratic non-residue modulo \(p\) and we have \(e_{f,1} = e_{f,p-1}\) and thus \(C({\mathcal F}) \le 1\). For \(d \ge 3\) it seems to be a challenging problem to estimate the family complexity of this family.
-
3.
Very recently, Gyarmati [5] proved also a lower bound on the family complexity of the family of sequences \(E_f\) defined by (5) where \(f\) runs through all monic irreducible polynomials of degree \(d\) (with arbitrary second leading coefficient). However, since \(f(X)\) is irreducible whenever \(f(X+c)\) for all \(c \in {\mathbb {F}}_p\), the cross-correlation measure of order 2 of this family is again very large.
References
Ahlswede, R., Khachatrian, L.H., Mauduit, C., Sárközy, A.: A complexity measure for families of binary sequences. Period. Math. Hung. 46(2), 107–118 (2003). MR 2004667 (2004j:11085)
Golomb, S.W., Gong, G.: Signal Design for Good Correlation. Cambridge University Press, Cambridge (2005). MR 2156522 (2006d:94021)
Goubin, L., Mauduit, C., Sárközy, A.: Construction of large families of pseudorandom binary sequences. J. Number Theory 106(1), 56–69 (2004). MR 2049592 (2004m:11121)
Gyarmati, K., Mauduit, C., Sárközy, A.: The cross correlation measure for families of binary sequences. In: Larcher, G., Pillichshammer, F., Winterhof, A., Xing, C. (eds.) Applications of Algebra and Number Theory. Cambridge University Press, Cambridge (to appear)
Gyarmati, K.: On the complexity of a family based on irreducible polynomials. Finite Fields Appl. (to appear)
Gyarmati, K.: On the complexity of a family related to the Legendre symbol. Period. Math. Hung. 58(2), 209–215 (2009). MR 2531165 (2010f:11131)
Gyarmati, K.: Measures of pseudorandomness. In: Charpin, P., Pott, A., Winterhof, A. (eds.) Finite Fields and Their Applications: Character Sums and Polynomials, Radon Series on Computation and Applied Mathematics, vol. 11, pp. 43–64. Walter de Gruyter, Berlin (2013)
Iwaniec, H., Kowalski, E.: Analytic Number Theory, American Mathematical Society Colloquium Publications, vol. 53. American Mathematical Society, Providence, RI (2004). MR 2061214 (2005h:11005)
Mauduit, C., Sárközy, A.: On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol. Acta Arith. 82(4), 365–377 (1997). MR 1483689 (99g:11095)
Tietäväinen, A.: Vinogradov’s Method and SomeApplications, Number Theory and Its Applications (Ankara, 1996),Lecture Notes in Pure and Applied Mathematics, vol. 204, pp. 261–282. Dekker, New York (1999). MR 1661670 (99k:11186)
Topuzoğlu, A., Winterhof, A.: Pseudorandom Sequences, Topics in Geometry, Coding Theory and Cryptography, Algebra Applications, vol. 6, pp. 135–166. Springer, Dordrecht (2007)
Winterhof, A.: Some estimates for character sums and applications. Des. Codes Cryptogr. 22(2), 123–131 (2001). MR 1813781 (2002g:11128)
Acknowledgments
The authors thank the anonymous referee for some useful comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
The first author is supported by the Austrian Science Fund (FWF): Project F5511-N26 which is part of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”. The second author is supported by the Scientific and Technological Research Council of Turkey (TÜBİTAK) under Grant No. 2219.
Rights and permissions
About this article
Cite this article
Winterhof, A., Yayla, O. Family complexity and cross-correlation measure for families of binary sequences. Ramanujan J 39, 639–645 (2016). https://doi.org/10.1007/s11139-014-9649-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11139-014-9649-5
Keywords
- Pseudorandomness
- Binary sequences
- Family complexity
- Cross-correlation measure
- Legendre sequence
- Polynomials over finite fields