-
Previous Article
Optimal strategies for CSIDH
- AMC Home
- This Issue
-
Next Article
Several new classes of (balanced) Boolean functions with few Walsh transform values
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 |
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 $.
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. |
[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. |
[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. 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. |
[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. |
[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. |
[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. 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. |
[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. |
[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. |
[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. |
[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. 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. |
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. |
[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. |
[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. 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. |
[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. |
[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. |
[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. 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. |
[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. |
[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. |
[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. |
[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. 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. |
[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]