# American Institute of Mathematical Sciences

doi: 10.3934/amc.2020100

## Binary sequences derived from differences of consecutive quadratic residues

 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$.

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, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334 [9] Stefano Galatolo. Orbit complexity and data compression. Discrete & Continuous Dynamical Systems, 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, 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, 2021, 41 (1) : 359-393. 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] 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 [15] 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 [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, 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] 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 [20] Valentin Afraimovich, Lev Glebsky. Measures related to $(\epsilon,n)$-complexity functions. Discrete & Continuous Dynamical Systems, 2008, 22 (1&2) : 23-34. doi: 10.3934/dcds.2008.22.23

2019 Impact Factor: 0.734