{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T14:11:44Z","timestamp":1783692704974,"version":"3.55.0"},"reference-count":54,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2023,12,1]]},"DOI":"10.1587\/transfun.2023sdi0001","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T22:14:39Z","timestamp":1685484879000},"page":"1452-1460","source":"Crossref","is-referenced-by-count":7,"title":["Pseudorandom Binary Sequences: Quality Measures and Number-Theoretic Constructions"],"prefix":"10.1587","volume":"E106.A","author":[{"given":"Arne","family":"WINTERHOF","sequence":"first","affiliation":[{"name":"Radon Institute for Computational and Applied Mathematics of the Austrian Academy of Sciences"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira, and V. R\u00f6dl, \u201cMeasures of pseudorandomness for finite sequences: Typical values,\u201d Proc. Lond. Math. Soc., vol.95, no.3, pp.778-812, 2007. 10.1112\/plms\/pdm027","DOI":"10.1112\/plms\/pdm027"},{"key":"2","unstructured":"[2] A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, and R. McConnell, \u201cLinear size finite automata for the set of all subwords of a word: An outline of results,\u201d Bul. Eur. Assoc. Theor. Comp. Sci., vol.21, pp.12-20, 1983."},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] N. Brandst\u00e4tter and A. Winterhof, \u201cSome notes on the two-prime generator of order 2,\u201d IEEE Trans. Inf. Theory, vol.51, no.10, pp.3654-3657, 2005. 10.1109\/tit.2005.855615","DOI":"10.1109\/TIT.2005.855615"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] N. Brandst\u00e4tter and A. Winterhof, \u201cLinear complexity profile of binary sequences with small correlation measure,\u201d Period. Math. Hungar., vol.52, no.2, pp.1-8, 2006. 10.1007\/s10998-006-0008-1","DOI":"10.1007\/s10998-006-0008-1"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] L. Carlitz, \u201cThe arithmetic of polynomials in a Galois field,\u201d Amer. J. Math. vol.54, no.1, pp.39-50, 1932. 10.2307\/2371075","DOI":"10.2307\/2371075"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] D. Carmon, \u201cThe autocorrelation of the M\u00f6bius function and Chowla&apos;s conjecture for the rational function field in characteristic 2,\u201d Philos. Trans. Roy. Soc. A, vol.373, no.2040, 20140311, 2015. 10.1098\/rsta.2014.0311","DOI":"10.1098\/rsta.2014.0311"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] D. Carmon and Z. Rudnick, \u201cThe autocorrelation of the M\u00f6bius function and Chowla&apos;s conjecture for the rational function field,\u201d Q.J. Math. vol.65, no.1, pp.53-61, 2014. 10.1093\/qmath\/has047","DOI":"10.1093\/qmath\/has047"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] J. Cassaigne, S. Ferenczi, C. Mauduit, J. Rivat, and A. S\u00e1rk\u00f6zy, \u201cOn finite pseudorandom binary sequences III: The Liouville function, I,\u201d Acta Arith., vol.87, no.4, pp.367-390, 1999. 10.4064\/aa-87-4-367-390","DOI":"10.4064\/aa-87-4-367-390"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] Z. Chen, A.I. G\u00f3mez, D. G\u00f3mez-P\u00e9rez, and A. Tirkel, \u201cCorrelation measure, linear complexity and maximum order complexity for families of binary sequences,\u201d Finite Fields Appl., vol.78, Paper no.101977, 2022. 10.1016\/j.ffa.2021.101977","DOI":"10.1016\/j.ffa.2021.101977"},{"key":"10","unstructured":"[10] S. Chowla, The Riemann Hypothesis and Hilbert&apos;s Tenth Problem, Mathematics and Its Applications, vol.4, Gordon and Breach Science Publishers, New York-London-Paris, 1965."},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] G. Christol, \u201cEnsembles presque p\u00e9riodiques <i>k<\/i>-reconnaissables,\u201d Theoret. Comput. Sci., vol.9, no.1, pp.141-145, 1979. 10.1016\/0304-3975(79)90011-2","DOI":"10.1016\/0304-3975(79)90011-2"},{"key":"12","unstructured":"[12] T.W. Cusick, C. Ding, and A. Renvall, Stream Ciphers and Number Theory, Revised edition, North-Holland Mathematical Library, 66, Elsevier Science B.V., Amsterdam, 2004."},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] C. Diem, \u201cOn the use of expansion series for stream ciphers,\u201d LMS J. Comput. Math., vol.15, pp.326-340, 2012. 10.1112\/s146115701200109x","DOI":"10.1112\/S146115701200109X"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] C. Ding, T. Helleseth, and W. Shan, \u201cOn the linear complexity of Legendre sequences,\u201d IEEE Trans. Inf. Theory, vol.44, no.3, pp.1276-1278, 1998. 10.1109\/18.669398","DOI":"10.1109\/18.669398"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] M. Drmota, C. Mauduit, and J. Rivat, \u201cNormality along squares,\u201d J. Eur. Math. Soc. (JEMS), vol.21, no.2, pp.507-548, 2019. 10.4171\/jems\/843","DOI":"10.4171\/JEMS\/843"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] K. Gyarmati, \u201cMeasures of pseudorandomness,\u201d Finite Fields and Their Applications, pp.43-64, De Gruyter, Berlin, 2013. 10.1515\/9783110283600.43","DOI":"10.1515\/9783110283600.43"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[18] D. G\u00f3mez-P\u00e9rez and L. M\u00e9rai, \u201cAlgebraic dependence in generating functions and expansion complexity,\u201d Adv. Math. Commun., vol.14, no.2, pp.307-318, 2020. 10.3934\/amc.2020022","DOI":"10.3934\/amc.2020022"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[19] D. G\u00f3mez-P\u00e9rez, L. M\u00e9rai, and H. Niederreiter, \u201cOn the expansion complexity of sequences over finite fields,\u201d IEEE Trans. Inf. Theory, vol.64, no.6, pp.4228-4232, 2018. 10.1109\/tit.2018.2792490","DOI":"10.1109\/TIT.2018.2792490"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[20] F.G. Gustavson, \u201cAnalysis of the Berlekamp-Massey linear feedback shift-register synthesis algorithm,\u201d IBM J. Res. Develop., vol.20, no.3, pp.204-212, 1976. 10.1147\/rd.203.0204","DOI":"10.1147\/rd.203.0204"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[21] R. Hofer and A. Winterhof, \u201cOn the 2-adic complexity of the two-prime generator,\u201d IEEE Trans. Inf. Theory, vol.64, no.8, pp.5957-5960, 2018. 10.1109\/tit.2018.2811507","DOI":"10.1109\/TIT.2018.2811507"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[22] R. Hofer, L. M\u00e9rai, and A. Winterhof, \u201cMeasures of pseudorandomness: Arithmetic autocorrelation and correlation measure,\u201d Number Theory \u2014 Diophantine Problems, Uniform Distribution and Applications, pp.303-312, Springer, Cham, 2017. 10.1007\/978-3-319-55357-3_15","DOI":"10.1007\/978-3-319-55357-3_15"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[23] R. Hofer and A. Winterhof, \u201cOn the arithmetic autocorrelation of the Legendre sequence,\u201d Adv. Math. Commun., vol.11, no.1, pp.237-244, 2017. 10.3934\/amc.2017015","DOI":"10.3934\/amc.2017015"},{"key":"23","doi-asserted-by":"publisher","unstructured":"[24] H. Hu, \u201cComments on \u2018A new method to compute the 2-adic complexity of binary sequences\u2019,\u201d IEEE Trans. Inf. Theory, vol.60, no.9, pp.5803-5804, 2014. 10.1109\/tit.2014.2336843","DOI":"10.1109\/TIT.2014.2336843"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[25] P. Humphries, \u201cThe distribution of weighted sums of the Liouville function and P\u00f3lya&apos;s conjecture,\u201d J. Number Theory, vol.133, no.2, pp.545-582, 2013. 10.1016\/j.jnt.2012.08.011","DOI":"10.1016\/j.jnt.2012.08.011"},{"key":"25","doi-asserted-by":"crossref","unstructured":"[26] H. Iwaniec and E. Kowalski, Analytic Number Theory, American Mathematical Society Colloquium Publications, 53, American Mathematical Society, Providence, RI, 2004.","DOI":"10.1090\/coll\/053"},{"key":"26","unstructured":"[27] C.J.A. Jansen, \u201cInvestigations on nonlinear streamcipher systems: Construction and evaluation methods,\u201d Ph.D. thesis, Technische Universiteit Delft (The Netherlands), ProQuest LLC, Ann Arbor, MI, 1989."},{"key":"27","doi-asserted-by":"crossref","unstructured":"[28] C.J.A. Jansen and D.E. Boekee, \u201cThe shortest feedback shift register that can generate a given sequence,\u201d Advances in Cryptology \u2014 CRYPTO&apos;89 (Santa Barbara, CA, 1989), Lecture Notes in Comput. Sci., vol.435, pp.90-99, 1990. 10.1007\/0-387-34805-0_10","DOI":"10.1007\/0-387-34805-0_10"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[29] A. Klapper, \u201cOpen problems on with-carry sequence generators,\u201d Open Problems in Mathematics and Computational Science, pp.181-201, Springer, Cham, 2014. 10.1007\/978-3-319-10683-0_9","DOI":"10.1007\/978-3-319-10683-0_9"},{"key":"29","doi-asserted-by":"publisher","unstructured":"[30] K. Limniotis, N. Kolokotronis, and N. Kalouptsidis, \u201cOn the nonlinear complexity and Lempel-Ziv complexity of finite length sequences,\u201d IEEE Trans. Inf. Theory, vol.53, no.11, pp.4293-4302, 2007. 10.1109\/tit.2007.907442","DOI":"10.1109\/TIT.2007.907442"},{"key":"30","doi-asserted-by":"publisher","unstructured":"[31] J.L. Massey, \u201cShift-register synthesis and BCH decoding,\u201d IEEE Trans. Inf. Theory, vol.15, no.1, pp.122-127, 1969. 10.1109\/tit.1969.1054260","DOI":"10.1109\/TIT.1969.1054260"},{"key":"31","doi-asserted-by":"publisher","unstructured":"[32] C. Mauduit and J. Rivat, \u201cLa somme des chiffres des carr\u00e9s,\u201d Acta Math., vol.203, no.1, pp.107-148, 2009. 10.1007\/s11511-009-0040-0","DOI":"10.1007\/s11511-009-0040-0"},{"key":"32","doi-asserted-by":"publisher","unstructured":"[33] C. Mauduit and A. S\u00e1rk\u00f6zy, \u201cOn finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol,\u201d Acta Arith., vol.82, no.4, pp.365-377, 1997. 10.4064\/aa-82-4-365-377","DOI":"10.4064\/aa-82-4-365-377"},{"key":"33","doi-asserted-by":"publisher","unstructured":"[34] C. Mauduit and A. S\u00e1rk\u00f6zy, \u201cOn finite pseudorandom binary sequences: II. The champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction,\u201d J. Number Theory, vol.73, no.2, pp.256-276, 1998. 10.1006\/jnth.1998.2286","DOI":"10.1006\/jnth.1998.2286"},{"key":"34","doi-asserted-by":"publisher","unstructured":"[35] W. Meidl and H. Niederreiter, \u201cOn the expected value of the linear complexity and the k-error linear complexity of periodic sequences,\u201d IEEE Trans. Inf. Theory, vol.48, no.11, pp.2817-2825, 2002. 10.1109\/tit.2002.804050","DOI":"10.1109\/TIT.2002.804050"},{"key":"35","doi-asserted-by":"publisher","unstructured":"[36] L. M\u00e9rai, H. Niederreiter, and A. Winterhof, \u201cExpansion complexity and linear complexity of sequences over finite fields,\u201d Cryptogr. Commun., vol.9, no.4, pp.501-509, 2017. 10.1007\/s12095-016-0189-2","DOI":"10.1007\/s12095-016-0189-2"},{"key":"36","doi-asserted-by":"publisher","unstructured":"[37] L. M\u00e9rai and A. Winterhof, \u201cOn the pseudorandomness of the Liouville function of polynomials over a finite field,\u201d Unif. Distrib. Theory, vol.11, no.1, pp.47-58, 2016. 10.1515\/udt-2016-0004","DOI":"10.1515\/udt-2016-0004"},{"key":"37","doi-asserted-by":"publisher","unstructured":"[38] L. M\u00e9rai and A. Winterhof, \u201cOn the <i>N<\/i>th linear complexity of automatic sequences,\u201d J. Number Theory, vol.187, pp.415-429, 2018. 10.1016\/j.jnt.2017.11.008","DOI":"10.1016\/j.jnt.2017.11.008"},{"key":"38","doi-asserted-by":"publisher","unstructured":"[39] L. M\u00e9rai and A. Winterhof, \u201cPseudorandom sequences derived from automatic sequences,\u201d Cryptogr. Commun., vol.14, no.4, pp.783-815, 2022. 10.1007\/s12095-022-00556-9","DOI":"10.1007\/s12095-022-00556-9"},{"key":"39","unstructured":"[40] G.L. Mullen and D. Panario, eds., Handbook of Finite Fields, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2013."},{"key":"40","doi-asserted-by":"crossref","unstructured":"[41] H. Niederreiter, \u201cThe probabilistic theory of linear complexity,\u201d Advances in Cryptology \u2014 EUROCRYPT&apos;88, volume 330 of Lecture Notes in Comput. Sci., pp.191-209, 1988. 10.1007\/3-540-45961-8_17","DOI":"10.1007\/3-540-45961-8_17"},{"key":"41","doi-asserted-by":"crossref","unstructured":"[42] H. Niederreiter, Linear complexity and related complexity measures for sequences. Progress in cryptology \u2014 INDOCRYPT 2003, Lecture Notes in Comput. Sci., vol.2904, pp.1-17, 2003. 10.1007\/978-3-540-24582-7_1","DOI":"10.1007\/978-3-540-24582-7_1"},{"key":"42","doi-asserted-by":"publisher","unstructured":"[43] D. Panario, L. Perin, and B. Stevens, \u201cComparing balanced sequences obtained from ElGamal function to random balanced sequences,\u201d Cyptogr. Commun., vol.15, pp.675-707, 2023. 10.1007\/s12095-022-00623-1","DOI":"10.1007\/s12095-022-00623-1"},{"key":"43","doi-asserted-by":"publisher","unstructured":"[44] P. Popoli, \u201cOn the maximum order complexity of Thue-Morse and Rudin-Shapiro sequences along polynomial values,\u201d Unif. Distrib. Theory, vol.15, no.2, pp.9-22, 2020. 10.2478\/udt-2020-0008","DOI":"10.2478\/udt-2020-0008"},{"key":"44","doi-asserted-by":"crossref","unstructured":"[45] W. Qi and H. Xu, \u201cOn the linear complexity of FCSR sequences,\u201d Appl. Math. J. Chinese Univ. Ser. B, vol.18, no.3, pp.318-324, 2003. 10.1007\/s11766-003-0057-7","DOI":"10.1007\/s11766-003-0057-7"},{"key":"45","doi-asserted-by":"publisher","unstructured":"[46] J. Rivat and A. S\u00e1rk\u00f6zy, \u201cModular constructions of pseudorandom binary sequences with composite moduli,\u201d Period. Math. Hungar., vol.51, no.2, pp.75-107, 2005. 10.1007\/s10998-005-0031-7","DOI":"10.1007\/s10998-005-0031-7"},{"key":"46","doi-asserted-by":"publisher","unstructured":"[47] W. Sawin and M. Shusterman, \u201cOn the Chowla and twin primes conjectures over \ud835\udd3d<i><sub>q<\/sub><\/i>[<i>T<\/i>],\u201d Ann. of Math., vol.196, no.2, pp.457-506, 2022. 10.4007\/annals.2022.196.2.1","DOI":"10.4007\/annals.2022.196.2.1"},{"key":"47","doi-asserted-by":"publisher","unstructured":"[48] T. Tao and J. Ter\u00e4v\u00e4inen, \u201cThe structure of logarithmically averaged correlations of multiplicative functions, with applications to the Chowla and Elliott conjectures,\u201d Duke Math. J., vol.168, no.11, pp.1977-2027, 2019. 10.1215\/00127094-2019-0002","DOI":"10.1215\/00127094-2019-0002"},{"key":"48","doi-asserted-by":"publisher","unstructured":"[49] T. Tao and J. Ter\u00e4v\u00e4inen, \u201cThe structure of correlations of multiplicative functions at almost all scales, with applications to the Chowla and Elliott conjectures,\u201d Algebra Number Theory, vol.13, no.9, pp.2103-2150, 2019. 10.2140\/ant.2019.13.2103","DOI":"10.2140\/ant.2019.13.2103"},{"key":"49","doi-asserted-by":"publisher","unstructured":"[50] Z. Sun and A. Winterhof, \u201cOn the maximum order complexity of the Thue-Morse and Rudin-Shapiro sequence,\u201d Unif. Distrib. Theory, vol.14, no.2, pp.33-42, 2019. 10.2478\/udt-2019-0012","DOI":"10.2478\/udt-2019-0012"},{"key":"50","doi-asserted-by":"publisher","unstructured":"[51] Z. Sun and A. Winterhof, \u201cOn the maximum order complexity of subsequences of the Thue-Morse and Rudin-Shapiro sequence along squares,\u201d Int. J. Comput. Math. Comput. Syst. Theory, vol.4, no.1, pp.30-36, 2019. 10.1080\/23799927.2019.1566275","DOI":"10.1080\/23799927.2019.1566275"},{"key":"51","doi-asserted-by":"crossref","unstructured":"[52] A. Topuzo\u011flu and A. Winterhof, \u201cPseudorandom sequences,\u201d Topics in Geometry, Coding Theory and Cryptography, Algebr. Appl., vol.6, pp.135-166, 2007. 10.1007\/1-4020-5334-4_4","DOI":"10.1007\/1-4020-5334-4_4"},{"key":"52","doi-asserted-by":"publisher","unstructured":"[53] R.J. Turyn, \u201cThe linear generation of Legendre sequence,\u201d J. Soc. Indust. Appl. Math., vol.12, no.1, pp.115-116, 1964. 10.1137\/0112010","DOI":"10.1137\/0112010"},{"key":"53","doi-asserted-by":"crossref","unstructured":"[54] A. Winterhof, \u201cLinear complexity and related complexity measures,\u201d Selected Topics in Information and Coding Theory, pp.3-40, 2010. 10.1142\/9789812837172_0001","DOI":"10.1142\/9789812837172_0001"},{"key":"54","doi-asserted-by":"publisher","unstructured":"[55] H. Xiong, L. Qu, and C. Li, \u201cA new method to compute the 2-adic complexity of binary sequences,\u201d IEEE Trans. Inf. Theory, vol.60, no.4, pp.2399-2406, 2014. 10.1109\/tit.2014.2304451","DOI":"10.1109\/TIT.2014.2304451"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E106.A\/12\/E106.A_2023SDI0001\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,2]],"date-time":"2023-12-02T04:07:27Z","timestamp":1701490047000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E106.A\/12\/E106.A_2023SDI0001\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,1]]},"references-count":54,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2023sdi0001","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,1]]},"article-number":"2023SDI0001"}}