{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T22:55:55Z","timestamp":1770072955776,"version":"3.49.0"},"reference-count":18,"publisher":"American Institute of Mathematical Sciences (AIMS)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AMC"],"published-print":{"date-parts":[[2022]]},"abstract":"<p style='text-indent:20px;'>For a prime <inline-formula><tex-math id=\"M1\">\\begin{document}$ p\\ge 5 $\\end{document}<\/tex-math><\/inline-formula> let <inline-formula><tex-math id=\"M2\">\\begin{document}$ q_0,q_1,\\ldots,q_{(p-3)\/2} $\\end{document}<\/tex-math><\/inline-formula> be the quadratic residues modulo <inline-formula><tex-math id=\"M3\">\\begin{document}$ p $\\end{document}<\/tex-math><\/inline-formula> in increasing order. We study two <inline-formula><tex-math id=\"M4\">\\begin{document}$ (p-3)\/2 $\\end{document}<\/tex-math><\/inline-formula>-periodic binary sequences <inline-formula><tex-math id=\"M5\">\\begin{document}$ (d_n) $\\end{document}<\/tex-math><\/inline-formula> and <inline-formula><tex-math id=\"M6\">\\begin{document}$ (t_n) $\\end{document}<\/tex-math><\/inline-formula> defined by <inline-formula><tex-math id=\"M7\">\\begin{document}$ d_n = q_n+q_{n+1}\\bmod 2 $\\end{document}<\/tex-math><\/inline-formula> and <inline-formula><tex-math id=\"M8\">\\begin{document}$ t_n = 1 $\\end{document}<\/tex-math><\/inline-formula> if <inline-formula><tex-math id=\"M9\">\\begin{document}$ q_{n+1} = q_n+1 $\\end{document}<\/tex-math><\/inline-formula> and <inline-formula><tex-math id=\"M10\">\\begin{document}$ t_n = 0 $\\end{document}<\/tex-math><\/inline-formula> otherwise, <inline-formula><tex-math id=\"M11\">\\begin{document}$ n = 0,1,\\ldots,(p-5)\/2 $\\end{document}<\/tex-math><\/inline-formula>. For both sequences we find some sufficient conditions for attaining the maximal linear complexity <inline-formula><tex-math id=\"M12\">\\begin{document}$ (p-3)\/2 $\\end{document}<\/tex-math><\/inline-formula>.<\/p><p style='text-indent:20px;'>Studying the linear complexity of <inline-formula><tex-math id=\"M13\">\\begin{document}$ (d_n) $\\end{document}<\/tex-math><\/inline-formula> was motivated by heuristics of Caragiu et al. However, <inline-formula><tex-math id=\"M14\">\\begin{document}$ (d_n) $\\end{document}<\/tex-math><\/inline-formula> is not balanced and we show that a period of <inline-formula><tex-math id=\"M15\">\\begin{document}$ (d_n) $\\end{document}<\/tex-math><\/inline-formula> contains about <inline-formula><tex-math id=\"M16\">\\begin{document}$ 1\/3 $\\end{document}<\/tex-math><\/inline-formula> zeros and <inline-formula><tex-math id=\"M17\">\\begin{document}$ 2\/3 $\\end{document}<\/tex-math><\/inline-formula> ones if <inline-formula><tex-math id=\"M18\">\\begin{document}$ p $\\end{document}<\/tex-math><\/inline-formula> is sufficiently large. In contrast, <inline-formula><tex-math id=\"M19\">\\begin{document}$ (t_n) $\\end{document}<\/tex-math><\/inline-formula> is not only essentially balanced but also all longer patterns of length <inline-formula><tex-math id=\"M20\">\\begin{document}$ s $\\end{document}<\/tex-math><\/inline-formula> appear essentially equally often in the vector sequence <inline-formula><tex-math id=\"M21\">\\begin{document}$ (t_n,t_{n+1},\\ldots,t_{n+s-1}) $\\end{document}<\/tex-math><\/inline-formula>, <inline-formula><tex-math id=\"M22\">\\begin{document}$ n = 0,1,\\ldots,(p-5)\/2 $\\end{document}<\/tex-math><\/inline-formula>, for any fixed <inline-formula><tex-math id=\"M23\">\\begin{document}$ s $\\end{document}<\/tex-math><\/inline-formula> and sufficiently large <inline-formula><tex-math id=\"M24\">\\begin{document}$ p $\\end{document}<\/tex-math><\/inline-formula>.<\/p><\/jats:p>","DOI":"10.3934\/amc.2020100","type":"journal-article","created":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T11:23:41Z","timestamp":1596453821000},"page":"83","source":"Crossref","is-referenced-by-count":2,"title":["Binary sequences derived from differences of consecutive quadratic residues"],"prefix":"10.3934","volume":"16","author":[{"given":"Arne","family":"Winterhof","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zibi","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"2321","reference":[{"key":"key-10.3934\/amc.2020100-1","doi-asserted-by":"publisher","unstructured":"N. Alon, Y Kohayakawa, C. Mauduit, C. G. Moreira, V. R\u00f6dl.Measures of pseudorandomness for finite sequences: typical values, Proc. Lond. Math. Soc.<\/i>, 95<\/b> (2007), 778-812.","DOI":"10.1112\/plms\/pdm027"},{"key":"key-10.3934\/amc.2020100-2","doi-asserted-by":"publisher","unstructured":"M. Caragiu, S. Tefft, A. Kemats, T. Maenle.A linear complexity analysis of quadratic residues and primitive roots spacings, Far East J. Math. Ed.<\/i>, 19<\/b> (2019), 27-37.","DOI":"10.17654\/ME019010027"},{"key":"key-10.3934\/amc.2020100-3","unstructured":"T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory<\/i>, Elsevier Science B. V., Amsterdam, 2004."},{"key":"key-10.3934\/amc.2020100-4","doi-asserted-by":"publisher","unstructured":"C. Ding.Pattern distributions of Legendre sequences, IEEE Trans. Inform. Theory<\/i>, 44<\/b> (1998), 1693-1698.","DOI":"10.1109\/18.681353"},{"key":"key-10.3934\/amc.2020100-5","doi-asserted-by":"publisher","unstructured":"O. Geil, F. \u00d6zbudak, D. Ruano.Constructing sequences with high nonlinear complexity using the Weierstrass semigroup of a pair of distinct points of a Hermitian curve, Semigroup Forum<\/i>, 98<\/b> (2019), 543-555.","DOI":"10.1007\/s00233-018-9976-8"},{"key":"key-10.3934\/amc.2020100-6","doi-asserted-by":"crossref","unstructured":"L. I\u015f\u0131k, A. Winterhof.Maximum-order complexity and correlation measures, Cryptography<\/i>, 1<\/b> (2017), 1-7.","DOI":"10.3390\/cryptography1010007"},{"key":"key-10.3934\/amc.2020100-7","unstructured":"C. J. A. Jansen, Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods<\/i>, Ph.D thesis, Delft University of Technology, the Netherlands, 1989."},{"key":"key-10.3934\/amc.2020100-8","doi-asserted-by":"publisher","unstructured":"Y. Luo, C. Xing, L. You.Construction of sequences with high nonlinear complexity from function fields, IEEE Trans. Inform. Theory<\/i>, 63<\/b> (2017), 7646-7650.","DOI":"10.1109\/TIT.2017.2736545"},{"key":"key-10.3934\/amc.2020100-9","doi-asserted-by":"publisher","unstructured":"C. Mauduit, A. S\u00e1rk\u00f6zy.On finite pseudorandom sequences of $k$ symbols, Indag. Math.<\/i>, 13<\/b> (2002), 89-101.","DOI":"10.1016\/S0019-3577(02)90008-X"},{"key":"key-10.3934\/amc.2020100-10","unstructured":"W. Meidl, A. Winterhof., Linear complexity of sequences and multisequences<\/i>, ${ref.volume}<\/b> (2013)."},{"key":"key-10.3934\/amc.2020100-11","doi-asserted-by":"publisher","unstructured":"H. Niederreiter, Linear complexity and related complexity measures for sequences, In Progress in Cryptology-INDOCRYPT 2003<\/i>, Lecture Notes in Comput. Sci., volume 2904, Springer, Berlin, 2003, 1-17.","DOI":"10.1007\/978-3-540-24582-7_1"},{"key":"key-10.3934\/amc.2020100-12","doi-asserted-by":"publisher","unstructured":"J. Peng, X. Zeng, Z. Sun.Finite length sequences with large nonlinear complexity, Adv. Math. Commun.<\/i>, 12<\/b> (2018), 215-230.","DOI":"10.3934\/amc.2018015"},{"key":"key-10.3934\/amc.2020100-13","doi-asserted-by":"crossref","unstructured":"Z. Sun, A. Winterhof.On the maximum order complexity of the Thue-Morse and Rudin-Shapiro sequence, Unif. Distr. Th.<\/i>, 14<\/b> (2019), 33-42.","DOI":"10.2478\/udt-2019-0012"},{"key":"key-10.3934\/amc.2020100-14","doi-asserted-by":"publisher","unstructured":"Z. Sun, 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<\/i>, 4<\/b> (2019), 30-36.","DOI":"10.1080\/23799927.2019.1566275"},{"key":"key-10.3934\/amc.2020100-15","doi-asserted-by":"publisher","unstructured":"Z. Sun, X. Zeng, C. Li, T. Helleseth.Investigations on periodic sequences with maximum nonlinear complexity, IEEE Trans. Inform. Theory<\/i>, 63<\/b> (2017), 6188-6198.","DOI":"10.1109\/TIT.2017.2714681"},{"key":"key-10.3934\/amc.2020100-16","doi-asserted-by":"publisher","unstructured":"A. Topuzo\u01e7lu glu and A. Winterhof, Pseudorandom sequences, in Topics in Geometry, Coding Theory and Cryptography<\/i>, Algebr. Appl., volume 6, Springer, Dordrecht, (2007), 135-166.","DOI":"10.1007\/1-4020-5334-4_4"},{"key":"key-10.3934\/amc.2020100-17","doi-asserted-by":"publisher","unstructured":"A. Winterhof, Linear complexity and related complexity measures, in Selected Topics in Information and Coding Theory<\/i>, Ser. Coding Theory Cryptol., volume 7, World Sci. Publ., Hackensack, NJ, (2010), 3-40.","DOI":"10.1142\/9789812837172_0001"},{"key":"key-10.3934\/amc.2020100-18","doi-asserted-by":"publisher","unstructured":"Z. Xiao, X. Zeng, C. Li, Y. Jiang.Binary sequences with period $N$ and nonlinear complexity $N-2$, Cryptogr. Commun.<\/i>, 11<\/b> (2019), 735-757.","DOI":"10.1007\/s12095-018-0324-3"}],"container-title":["Advances in Mathematics of Communications"],"original-title":[],"link":[{"URL":"https:\/\/www.aimsciences.org\/article\/exportPdf?id=f3598c07-52a7-40e2-9dac-ff86a9dbbafe","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T11:44:30Z","timestamp":1640864670000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.aimsciences.org\/article\/doi\/10.3934\/amc.2020100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022]]}},"alternative-id":["1930-5346_2022_1_83"],"URL":"https:\/\/doi.org\/10.3934\/amc.2020100","relation":{},"ISSN":["1930-5346","1930-5338"],"issn-type":[{"value":"1930-5346","type":"print"},{"value":"1930-5338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]}}}