American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020100

Binary sequences derived from differences of consecutive quadratic residues

Arne Winterhof 1,, and  Zibi Xiao 2,

1. 

Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenbergerstr. 69, 4040 Linz, Austria
2. 

College of Science, Wuhan University of Science and Technology, Wuhan 430081, Hubei, China

* Corresponding author: Arne Winterhof

Received  March 2020 Revised  May 2020 Published  July 2020

Fund Project: The first author is partially supported by the Austrian Science Fund FWF Project P 30405-N32. The second author is supported by the Chinese Scholarship Council

For a prime $ p\ge 5 $ let $ q_0,q_1,\ldots,q_{(p-3)/2} $ be the quadratic residues modulo $ p $ in increasing order. We study two $ (p-3)/2 $-periodic binary sequences $ (d_n) $ and $ (t_n) $ defined by $ d_n = q_n+q_{n+1}\bmod 2 $ and $ t_n = 1 $ if $ q_{n+1} = q_n+1 $ and $ t_n = 0 $ otherwise, $ n = 0,1,\ldots,(p-5)/2 $. For both sequences we find some sufficient conditions for attaining the maximal linear complexity $ (p-3)/2 $.

Studying the linear complexity of $ (d_n) $ was motivated by heuristics of Caragiu et al. However, $ (d_n) $ is not balanced and we show that a period of $ (d_n) $ contains about $ 1/3 $ zeros and $ 2/3 $ ones if $ p $ is sufficiently large. In contrast, $ (t_n) $ is not only essentially balanced but also all longer patterns of length $ s $ appear essentially equally often in the vector sequence $ (t_n,t_{n+1},\ldots,t_{n+s-1}) $, $ n = 0,1,\ldots,(p-5)/2 $, for any fixed $ s $ and sufficiently large $ p $.

Keywords: Quadratic residues, sequences, linear complexity, pattern distribution, maximum order complexity.
Mathematics Subject Classification: Primary:94A55;Secondary:11T71.
Citation: Arne Winterhof, Zibi Xiao. Binary sequences derived from differences of consecutive quadratic residues. Advances in Mathematics of Communications, doi: 10.3934/amc.2020100
References:
[1]

N. Alon, Y Kohayakawa, C. Mauduit, C. G. Moreira and V. Rödl, Measures of pseudorandomness for finite sequences: typical values, Proc. Lond. Math. Soc., 95 (2007), 778-812.  doi: 10.1112/plms/pdm027.  Google Scholar

[2]

M. Caragiu, S. Tefft, A. Kemats and T. Maenle, A linear complexity analysis of quadratic residues and primitive roots spacings, Far East J. Math. Ed., 19 (2019), 27-37.  doi: 10.17654/ME019010027.  Google Scholar

[3]

T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier Science B. V., Amsterdam, 2004.  Google Scholar

[4]

C. Ding, Pattern distributions of Legendre sequences, IEEE Trans. Inform. Theory, 44 (1998), 1693-1698.  doi: 10.1109/18.681353.  Google Scholar

[5]

O. Geil, F. Özbudak and D. Ruano, Constructing sequences with high nonlinear complexity using the Weierstrass semigroup of a pair of distinct points of a Hermitian curve, Semigroup Forum, 98 (2019), 543-555.  doi: 10.1007/s00233-018-9976-8.  Google Scholar

[6]

L. Işık and A. Winterhof, Maximum-order complexity and correlation measures, Cryptography, 1 (2017), 1-7.   Google Scholar

[7]

C. J. A. Jansen, Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods, Ph.D thesis, Delft University of Technology, the Netherlands, 1989.  Google Scholar

[8]

Y. Luo, C. Xing and L. You, Construction of sequences with high nonlinear complexity from function fields, IEEE Trans. Inform. Theory, 63 (2017), 7646-7650.  doi: 10.1109/TIT.2017.2736545.  Google Scholar

[9]

C. Mauduit and A. Sárközy, On finite pseudorandom sequences of $k$ symbols, Indag. Math., 13 (2002), 89-101.  doi: 10.1016/S0019-3577(02)90008-X.  Google Scholar

[10] W. Meidl and A. Winterhof, Linear complexity of sequences and multisequences, In Handbook of Finite Fields, CRC Press, 2013.   Google Scholar
[11]

H. Niederreiter, Linear complexity and related complexity measures for sequences, In Progress in Cryptology-INDOCRYPT 2003, Lecture Notes in Comput. Sci., volume 2904, Springer, Berlin, 2003, 1-17. doi: 10.1007/978-3-540-24582-7_1.  Google Scholar

[12]

J. Peng, X. Zeng and Z. Sun, Finite length sequences with large nonlinear complexity, Adv. Math. Commun., 12 (2018), 215-230.  doi: 10.3934/amc.2018015.  Google Scholar

[13]

Z. Sun and A. Winterhof, On the maximum order complexity of the Thue-Morse and Rudin-Shapiro sequence, Unif. Distr. Th., 14 (2019), 33-42.   Google Scholar

[14]

Z. Sun and A. Winterhof, On the maximum order complexity of subsequences of the Thue-Morse and Rudin-Shapiro sequence along squares, Int. J. Comput. Math. Comput. Syst. Theory, 4 (2019), 30-36.  doi: 10.1080/23799927.2019.1566275.  Google Scholar

[15]

Z. Sun, X. Zeng, C. Li and T. Helleseth, Investigations on periodic sequences with maximum nonlinear complexity, IEEE Trans. Inform. Theory, 63 (2017), 6188-6198.  doi: 10.1109/TIT.2017.2714681.  Google Scholar

[16]

A. Topuzoǧlu glu and A. Winterhof, Pseudorandom sequences, in Topics in Geometry, Coding Theory and Cryptography, Algebr. Appl., volume 6, Springer, Dordrecht, (2007), 135-166. doi: 10.1007/1-4020-5334-4_4.  Google Scholar

[17]

A. Winterhof, Linear complexity and related complexity measures, in Selected Topics in Information and Coding Theory, Ser. Coding Theory Cryptol., volume 7, World Sci. Publ., Hackensack, NJ, (2010), 3-40. doi: 10.1142/9789812837172_0001.  Google Scholar

[18]

Z. Xiao, X. Zeng, C. Li and Y. Jiang, Binary sequences with period $N$ and nonlinear complexity $N-2$, Cryptogr. Commun., 11 (2019), 735-757.  doi: 10.1007/s12095-018-0324-3.  Google Scholar

show all references

References:
[1]

N. Alon, Y Kohayakawa, C. Mauduit, C. G. Moreira and V. Rödl, Measures of pseudorandomness for finite sequences: typical values, Proc. Lond. Math. Soc., 95 (2007), 778-812.  doi: 10.1112/plms/pdm027.  Google Scholar

[2]

M. Caragiu, S. Tefft, A. Kemats and T. Maenle, A linear complexity analysis of quadratic residues and primitive roots spacings, Far East J. Math. Ed., 19 (2019), 27-37.  doi: 10.17654/ME019010027.  Google Scholar

[3]

T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier Science B. V., Amsterdam, 2004.  Google Scholar

[4]

C. Ding, Pattern distributions of Legendre sequences, IEEE Trans. Inform. Theory, 44 (1998), 1693-1698.  doi: 10.1109/18.681353.  Google Scholar

[5]

O. Geil, F. Özbudak and D. Ruano, Constructing sequences with high nonlinear complexity using the Weierstrass semigroup of a pair of distinct points of a Hermitian curve, Semigroup Forum, 98 (2019), 543-555.  doi: 10.1007/s00233-018-9976-8.  Google Scholar

[6]

L. Işık and A. Winterhof, Maximum-order complexity and correlation measures, Cryptography, 1 (2017), 1-7.   Google Scholar

[7]

C. J. A. Jansen, Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods, Ph.D thesis, Delft University of Technology, the Netherlands, 1989.  Google Scholar

[8]

Y. Luo, C. Xing and L. You, Construction of sequences with high nonlinear complexity from function fields, IEEE Trans. Inform. Theory, 63 (2017), 7646-7650.  doi: 10.1109/TIT.2017.2736545.  Google Scholar

[9]

C. Mauduit and A. Sárközy, On finite pseudorandom sequences of $k$ symbols, Indag. Math., 13 (2002), 89-101.  doi: 10.1016/S0019-3577(02)90008-X.  Google Scholar

[10] W. Meidl and A. Winterhof, Linear complexity of sequences and multisequences, In Handbook of Finite Fields, CRC Press, 2013.   Google Scholar
[11]

H. Niederreiter, Linear complexity and related complexity measures for sequences, In Progress in Cryptology-INDOCRYPT 2003, Lecture Notes in Comput. Sci., volume 2904, Springer, Berlin, 2003, 1-17. doi: 10.1007/978-3-540-24582-7_1.  Google Scholar

[12]

J. Peng, X. Zeng and Z. Sun, Finite length sequences with large nonlinear complexity, Adv. Math. Commun., 12 (2018), 215-230.  doi: 10.3934/amc.2018015.  Google Scholar

[13]

Z. Sun and A. Winterhof, On the maximum order complexity of the Thue-Morse and Rudin-Shapiro sequence, Unif. Distr. Th., 14 (2019), 33-42.   Google Scholar

[14]

Z. Sun and A. Winterhof, On the maximum order complexity of subsequences of the Thue-Morse and Rudin-Shapiro sequence along squares, Int. J. Comput. Math. Comput. Syst. Theory, 4 (2019), 30-36.  doi: 10.1080/23799927.2019.1566275.  Google Scholar

[15]

Z. Sun, X. Zeng, C. Li and T. Helleseth, Investigations on periodic sequences with maximum nonlinear complexity, IEEE Trans. Inform. Theory, 63 (2017), 6188-6198.  doi: 10.1109/TIT.2017.2714681.  Google Scholar

[16]

A. Topuzoǧlu glu and A. Winterhof, Pseudorandom sequences, in Topics in Geometry, Coding Theory and Cryptography, Algebr. Appl., volume 6, Springer, Dordrecht, (2007), 135-166. doi: 10.1007/1-4020-5334-4_4.  Google Scholar

[17]

A. Winterhof, Linear complexity and related complexity measures, in Selected Topics in Information and Coding Theory, Ser. Coding Theory Cryptol., volume 7, World Sci. Publ., Hackensack, NJ, (2010), 3-40. doi: 10.1142/9789812837172_0001.  Google Scholar

[18]

Z. Xiao, X. Zeng, C. Li and Y. Jiang, Binary sequences with period $N$ and nonlinear complexity $N-2$, Cryptogr. Commun., 11 (2019), 735-757.  doi: 10.1007/s12095-018-0324-3.  Google Scholar

[1]

Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297
[2]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[3]

Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047
[4]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016
[5]

Jiarong Peng, Xiangyong Zeng, Zhimin Sun. Finite length sequences with large nonlinear complexity. Advances in Mathematics of Communications, 2018, 12 (1) : 215-230. doi: 10.3934/amc.2018015
[6]

Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
[7]

Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369
[8]

Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020334
[9]

Stefano Galatolo. Orbit complexity and data compression. Discrete & Continuous Dynamical Systems - A, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477
[10]

Valentin Afraimovich, Lev Glebsky, Rosendo Vazquez. Measures related to metric complexity. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1299-1309. doi: 10.3934/dcds.2010.28.1299
[11]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020167
[12]

Lin Yi, Xiangyong Zeng, Zhimin Sun. On finite length nonbinary sequences with large nonlinear complexity over the residue ring $ \mathbb{Z}_{m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020091
[13]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[14]

Valentin Afraimovich, Maurice Courbage, Lev Glebsky. Directional complexity and entropy for lift mappings. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3385-3401. doi: 10.3934/dcdsb.2015.20.3385
[15]

Fedor Petrov, Zhi-Wei Sun. Proof of some conjectures involving quadratic residues. Electronic Research Archive, 2020, 28 (2) : 589-597. doi: 10.3934/era.2020031
[16]

Shaolin Ji, Xiaole Xue. A stochastic maximum principle for linear quadratic problem with nonconvex control domain. Mathematical Control & Related Fields, 2019, 9 (3) : 495-507. doi: 10.3934/mcrf.2019022
[17]

Roland Zweimüller. Asymptotic orbit complexity of infinite measure preserving transformations. Discrete & Continuous Dynamical Systems - A, 2006, 15 (1) : 353-366. doi: 10.3934/dcds.2006.15.353
[18]

Erik M. Bollt, Joseph D. Skufca, Stephen J . McGregor. Control entropy: A complexity measure for nonstationary signals. Mathematical Biosciences & Engineering, 2009, 6 (1) : 1-25. doi: 10.3934/mbe.2009.6.1
[19]

Enrico Capobianco. Born to be big: Data, graphs, and their entangled complexity. Big Data & Information Analytics, 2016, 1 (2&3) : 163-169. doi: 10.3934/bdia.2016002
[20]

Easton Li Xu, Weiping Shang, Guangyue Han. Network encoding complexity: Exact values, bounds, and inequalities. Advances in Mathematics of Communications, 2017, 11 (3) : 567-594. doi: 10.3934/amc.2017044

2019 Impact Factor: 0.734

Tools

Article outline

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences