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]

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

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007
[3]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025
[4]

Lars Grüne, Roberto Guglielmi. On the relation between turnpike properties and dissipativity for continuous time linear quadratic optimal control problems. Mathematical Control & Related Fields, 2021, 11 (1) : 169-188. doi: 10.3934/mcrf.2020032
[5]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026
[6]

Andreu Ferré Moragues. Properties of multicorrelation sequences and large returns under some ergodicity assumptions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020386
[7]

Kalikinkar Mandal, Guang Gong. On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020125
[8]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374
[9]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048
[10]

Alexandra Köthe, Anna Marciniak-Czochra, Izumi Takagi. Hysteresis-driven pattern formation in reaction-diffusion-ODE systems. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3595-3627. doi: 10.3934/dcds.2020170
[11]

Hua Zhong, Xiaolin Fan, Shuyu Sun. The effect of surface pattern property on the advancing motion of three-dimensional droplets. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020366
[12]

Evelyn Sander, Thomas Wanner. Equilibrium validation in models for pattern formation based on Sobolev embeddings. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 603-632. doi: 10.3934/dcdsb.2020260
[13]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[14]

Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020364
[15]

Yunqing Zou, Zhengkui Lin, Dongya Han, T. C. Edwin Cheng, Chin-Chia Wu. Two-agent integrated scheduling of production and distribution operations with fixed departure times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021005
[16]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016
[17]

Stefan Doboszczak, Manil T. Mohan, Sivaguru S. Sritharan. Pontryagin maximum principle for the optimal control of linearized compressible navier-stokes equations with state constraints. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020110
[18]

Jinfeng Wang, Sainan Wu, Junping Shi. Pattern formation in diffusive predator-prey systems with predator-taxis and prey-taxis. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1273-1289. doi: 10.3934/dcdsb.2020162
[19]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[20]

Klemens Fellner, Jeff Morgan, Bao Quoc Tang. Uniform-in-time bounds for quadratic reaction-diffusion systems with mass dissipation in higher dimensions. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 635-651. doi: 10.3934/dcdss.2020334

2019 Impact Factor: 0.734

Tools

Article outline

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences