February  2022, 16(1): 83-93. 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  February 2022 Early access  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, 2022, 16 (1) : 83-93. doi: 10.3934/amc.2020100
References:
[1]

N. AlonY KohayakawaC. MauduitC. 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.

[2]

M. CaragiuS. TefftA. 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.

[3]

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

[4]

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

[5]

O. GeilF. Ö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.

[6]

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

[7]

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

[8]

Y. LuoC. 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.

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

[10] W. Meidl and A. Winterhof, Linear complexity of sequences and multisequences, In Handbook of Finite Fields, CRC Press, 2013. 
[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.

[12]

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

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

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

[15]

Z. SunX. ZengC. 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.

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

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

[18]

Z. XiaoX. ZengC. 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.

show all references

References:
[1]

N. AlonY KohayakawaC. MauduitC. 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.

[2]

M. CaragiuS. TefftA. 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.

[3]

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

[4]

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

[5]

O. GeilF. Ö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.

[6]

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

[7]

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

[8]

Y. LuoC. 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.

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

[10] W. Meidl and A. Winterhof, Linear complexity of sequences and multisequences, In Handbook of Finite Fields, CRC Press, 2013. 
[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.

[12]

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

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

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

[15]

Z. SunX. ZengC. 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.

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

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

[18]

Z. XiaoX. ZengC. 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.

[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]

Fuqing Sun, Qin Yue, Xia Li. on the 2-adic complexity of cyclotomic binary sequences of order three. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022049

[4]

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

[5]

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

[6]

Lin Yi, Xiangyong Zeng, Zhimin Sun, Shasha Zhang. On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $ 4p^n $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021019

[7]

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

[8]

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

[9]

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

[10]

Vladimir Edemskiy, Sofia Koltsova. Estimate of 4-adic complexity of unified quaternary sequences of length $ 2p $. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022048

[11]

Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334

[12]

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

[13]

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

[14]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete and Continuous Dynamical Systems, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

[15]

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, 2021, 15 (4) : 701-720. doi: 10.3934/amc.2020091

[16]

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 and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[17]

Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003

[18]

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

[19]

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

[20]

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

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (450)
  • HTML views (617)
  • Cited by (0)

Other articles
by authors

[Back to Top]