Family complexity and cross-correlation measure for families of binary sequences
详细信息 查看全文
- 作者：Arne Winterhof ; Oğuz Yayla
- 关键词：Pseudorandomness ; Binary sequences ; Family complexity ; Cross ; correlation measure ; Legendre sequence ; Polynomials over finite fields
- 刊名：The Ramanujan Journal
- 出版年：2016
- 出版时间：April 2016
- 年：2016
- 卷：39
- 期：3
- 页码：639-645
- 全文大小：359 KB
- 参考文献：1.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)MathSciNet CrossRef MATH
2.Golomb, S.W., Gong, G.: Signal Design for Good Correlation. Cambridge University Press, Cambridge (2005). MR 2156522 (2006d:94021)CrossRef MATH
3.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)MathSciNet CrossRef MATH
4.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)
5.Gyarmati, K.: On the complexity of a family based on irreducible polynomials. Finite Fields Appl. (to appear)
6.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)MathSciNet CrossRef MATH
7.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)
8.Iwaniec, H., Kowalski, E.: Analytic Number Theory, American Mathematical Society Colloquium Publications, vol. 53. American Mathematical Society, Providence, RI (2004). MR 2061214 (2005h:11005)
9.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)MathSciNet MATH
10.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)
11.Topuzoğlu, A., Winterhof, A.: Pseudorandom Sequences, Topics in Geometry, Coding Theory and Cryptography, Algebra Applications, vol. 6, pp. 135–166. Springer, Dordrecht (2007)
12.Winterhof, A.: Some estimates for character sums and applications. Des. Codes Cryptogr. 22(2), 123–131 (2001). MR 1813781 (2002g:11128) - 作者单位：Arne Winterhof (1)
Oğuz Yayla (1)
1. Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenbergerstr. 69, 4040, Linz, Austria - 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Number Theory
Field Theory and Polynomials
Combinatorics
Fourier Analysis
Functions of a Complex Variable - 出版者：Springer U.S.
- ISSN：1572-9303
文摘
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.