{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T15:48:04Z","timestamp":1758815284037,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,7,7]],"date-time":"2021-07-07T00:00:00Z","timestamp":1625616000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,7]],"date-time":"2021-07-07T00:00:00Z","timestamp":1625616000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cryptogr. Commun."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Automatic sequences are not suitable sequences for cryptographic applications since both their subword complexity and their expansion complexity are small, and their correlation measure of order 2 is large. These sequences are highly predictable despite having a large maximum order complexity. However, recent results show that polynomial subsequences of automatic sequences, such as the Thue\u2013Morse sequence, are better candidates for pseudorandom sequences. A natural generalization of automatic sequences are morphic sequences, given by a fixed point of a prolongeable morphism that is not necessarily uniform. In this paper we prove a lower bound for the maximum order complexity of the sum of digits function in Zeckendorf base which is an example of a morphic sequence. We also prove that the polynomial subsequences of this sequence keep large maximum order complexity, such as the Thue\u2013Morse sequence.<\/jats:p>","DOI":"10.1007\/s12095-021-00507-w","type":"journal-article","created":{"date-parts":[[2021,7,7]],"date-time":"2021-07-07T03:29:41Z","timestamp":1625628581000},"page":"791-814","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences"],"prefix":"10.1007","volume":"13","author":[{"given":"Damien","family":"Jamet","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4243-9180","authenticated-orcid":false,"given":"Pierre","family":"Popoli","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Stoll","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,7]]},"reference":[{"issue":"101761","key":"507_CR1","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ffa.2020.101761","volume":"68","author":"JP Allouche","year":"2020","unstructured":"Allouche, J.P., Han, G.N., Niederreiter, H.: Perfect linear complexity profile and apwenian sequences. Finite Fields Appl. 68(101761), 13 (2020). https:\/\/doi.org\/10.1016\/j.ffa.2020.101761","journal-title":"Finite Fields Appl."},{"key":"507_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546563","volume-title":"Automatic sequences","author":"JP Allouche","year":"2003","unstructured":"Allouche, J.P., Shallit, J.: Automatic sequences. Cambridge University Press, Cambridge (2003). https:\/\/doi.org\/10.1017\/CBO9780511546563. Theory, applications, generalizations"},{"key":"507_CR3","doi-asserted-by":"publisher","unstructured":"Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M.T., Seiferas, J.: The smallest automaton recognizing the subwords of a text. pp. 31\u201355. https:\/\/doi.org\/10.1016\/0304-3975(85)90157-4. Special issue: Eleventh international colloquium on automata, languages and programming (Antwerp, 1984) (1985)","DOI":"10.1016\/0304-3975(85)90157-4"},{"key":"507_CR4","first-page":"Art. B35b, appr","volume":"35","author":"V Bruy\u00e8re","year":"1995","unstructured":"Bruy\u00e8re, V.: Automata and numeration systems. S\u00e9m Lothar. Combin. 35, Art. B35b, approx. 19 (1995)","journal-title":"S\u00e9m Lothar. Combin."},{"issue":"3","key":"507_CR5","doi-asserted-by":"publisher","first-page":"969","DOI":"10.4007\/annals.2006.163.969","volume":"163","author":"Y Bugeaud","year":"2006","unstructured":"Bugeaud, Y., Mignotte, M., Siksek, S.: Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers. Ann. of Math. (2) 163(3), 969\u20131018 (2006). https:\/\/doi.org\/10.4007\/annals.2006.163.969","journal-title":"Ann. of Math. (2)"},{"issue":"1","key":"507_CR6","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(79)90011-2","volume":"9","author":"G Christol","year":"1979","unstructured":"Christol, G.: Ensembles presque periodiques k-reconnaissables. Theoret. Comput. Sci. 9(1), 141\u2013145 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90011-2","journal-title":"Theoret. Comput. Sci."},{"key":"507_CR7","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1112\/S146115701200109X","volume":"15","author":"C Diem","year":"2012","unstructured":"Diem, C.: On the use of expansion series for stream ciphers. LMS J. Comput. Math. 15, 326\u2013340 (2012). https:\/\/doi.org\/10.1112\/S146115701200109X","journal-title":"LMS J. Comput. Math."},{"issue":"2","key":"507_CR8","doi-asserted-by":"publisher","first-page":"507","DOI":"10.4171\/JEMS\/843","volume":"21","author":"M Drmota","year":"2019","unstructured":"Drmota, M., Mauduit, C., Rivat, J.: Normality along squares. J. Eur. Math. Soc. (JEMS) 21(2), 507\u2013548 (2019). https:\/\/doi.org\/10.4171\/JEMS\/843","journal-title":"J. Eur. Math. Soc. (JEMS)"},{"issue":"9","key":"507_CR9","doi-asserted-by":"publisher","first-page":"3679","DOI":"10.1090\/proc\/14015","volume":"146","author":"M Drmota","year":"2018","unstructured":"Drmota, M., M\u00fcllner, C., Spiegelhofer, L.: M\u00f6bius orthogonality for the Zeckendorf sum-of-digits function. Proc. Amer. Math. Soc. 146(9), 3679\u20133691 (2018). https:\/\/doi.org\/10.1090\/proc\/14015","journal-title":"Proc. Amer. Math. Soc."},{"key":"507_CR10","unstructured":"Golomb, S. W.: Shift register sequences. With portions co-authored by Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales. Holden-Day, Inc., San Francisco, Calif.-Cambridge-Amsterdam (1967)"},{"key":"507_CR11","doi-asserted-by":"publisher","unstructured":"I\u015f\u0131k, L., Winterhof, A.: Maximum-order complexity and correlation measures. Cryptography 1. https:\/\/doi.org\/10.3390\/cryptography1010007 (2017)","DOI":"10.3390\/cryptography1010007"},{"key":"507_CR12","unstructured":"Jansen, C.J.A.: Investigations on nonlinear streamcipher systems: Construction and evaluation methods. ProQuest LLC, Ann Arbor, MI. Thesis (Dr.) \u2013 Technische Universiteit Delft (The Netherlands) (1989)"},{"key":"507_CR13","doi-asserted-by":"crossref","unstructured":"Jansen, C.J.A.: The maximum order complexity of sequence ensembles. In: Davies, D.W. (ed.) Advances in Cryptology \u2014 EUROCRYPT \u201991, pp 153\u2013159. Springer, Berlin (1991)","DOI":"10.1007\/3-540-46416-6_13"},{"issue":"1-2","key":"507_CR14","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1023\/A:1015241900975","volume":"43","author":"C Mauduit","year":"2001","unstructured":"Mauduit, C.: Multiplicative properties of the Thue-Morse sequence. Period. Math. Hungar. 43(1-2), 137\u2013153 (2001). https:\/\/doi.org\/10.1023\/A:1015241900975","journal-title":"Period. Math. Hungar."},{"issue":"2","key":"507_CR15","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1006\/jnth.1998.2286","volume":"73","author":"C Mauduit","year":"1998","unstructured":"Mauduit, C., S\u00e1rk\u00f6zy, A.: On finite pseudorandom binary sequences. II. The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction. J. Number Theory 73(2), 256\u2013276 (1998). https:\/\/doi.org\/10.1006\/jnth.1998.2286","journal-title":"J. Number Theory"},{"issue":"4","key":"507_CR16","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s12095-016-0189-2","volume":"9","author":"L M\u00e9rai","year":"2017","unstructured":"M\u00e9rai, L., Niederreiter, H., Winterhof, A.: Expansion complexity and linear complexity of sequences over finite fields. Cryptogr. Commun. 9(4), 501\u2013509 (2017). https:\/\/doi.org\/10.1007\/s12095-016-0189-2","journal-title":"Cryptogr. Commun."},{"key":"507_CR17","doi-asserted-by":"crossref","unstructured":"M\u00e9rai, L., Winterhof, A.: Pseudorandom sequences derived from automatic sequences. arXiv:2105.030862105.03086 (2021)","DOI":"10.1007\/s12095-022-00556-9"},{"issue":"1","key":"507_CR18","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1090\/S0002-9947-1921-1501161-8","volume":"22","author":"HM Morse","year":"1921","unstructured":"Morse, H.M.: Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc. 22(1), 84\u2013100 (1921). https:\/\/doi.org\/10.2307\/1988844","journal-title":"Trans. Amer. Math. Soc."},{"issue":"1-2","key":"507_CR19","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.tcs.2007.10.015","volume":"389","author":"Y Moshe","year":"2007","unstructured":"Moshe, Y.: On the subword complexity of Thue-Morse polynomial extractions. Theoret. Comput. Sci. 389(1-2), 318\u2013329 (2007). https:\/\/doi.org\/10.1016\/j.tcs.2007.10.015","journal-title":"Theoret. Comput. Sci."},{"issue":"10","key":"507_CR20","doi-asserted-by":"publisher","first-page":"6696","DOI":"10.1109\/TIT.2014.2343225","volume":"60","author":"H Niederreiter","year":"2014","unstructured":"Niederreiter, H., Xing, C.: Sequences with high nonlinear complexity. IEEE Trans. Inform. Theory 60(10), 6696\u20136701 (2014). https:\/\/doi.org\/10.1109\/TIT.2014.2343225","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"2","key":"507_CR21","doi-asserted-by":"publisher","first-page":"9","DOI":"10.2478\/udt-2020-0008","volume":"15","author":"P Popoli","year":"2020","unstructured":"Popoli, P.: On the maximum order complexity of Thue-Morse and Rudin-Shapiro sequences along polynomial values. Unif. Distrib. Theory 15(2), 9\u201322 (2020). https:\/\/doi.org\/10.2478\/udt-2020-0008","journal-title":"Unif. Distrib. Theory"},{"key":"507_CR22","first-page":"225","volume":"33","author":"E Prouhet","year":"1851","unstructured":"Prouhet, E.: M\u00e9moire sur quelques relations entre les puissances des nombres. C. R. Acad. Sc. Paris 33, 225 (1851)","journal-title":"C. R. Acad. Sc. Paris"},{"key":"507_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0081890","volume-title":"Substitution dynamical systems\u2014spectral analysis. Lecture Notes in Mathematics, vol. 1294","author":"M Queff\u00e9lec","year":"1987","unstructured":"Queff\u00e9lec, M.: Substitution dynamical systems\u2014spectral analysis. Lecture Notes in Mathematics, vol. 1294. Springer, Berlin (1987). https:\/\/doi.org\/10.1007\/BFb0081890"},{"issue":"3","key":"507_CR24","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1016\/j.indag.2021.03.004","volume":"32","author":"J Shallit","year":"2021","unstructured":"Shallit, J.: Subword complexity of the Fibonacci-Thue-Morse sequence: The proof of Dekking\u2019s conjecture. Indag. Math. (N.S.) 32(3), 729\u2013735 (2021). https:\/\/doi.org\/10.1016\/j.indag.2021.03.004","journal-title":"Indag. Math. (N.S.)"},{"issue":"3","key":"507_CR25","first-page":"203","volume":"58","author":"A Shutov","year":"2020","unstructured":"Shutov, A.: On the sum of digits of the Zeckendorf representations of two consecutive numbers. Fibonacci Quart. 58(3), 203\u2013207 (2020)","journal-title":"Fibonacci Quart."},{"issue":"2","key":"507_CR26","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s11139-012-9422-6","volume":"32","author":"T Stoll","year":"2013","unstructured":"Stoll, T.: Combinatorial constructions for the Zeckendorf sum of digits of polynomial values. Ramanujan J. 32(2), 227\u2013243 (2013). https:\/\/doi.org\/10.1007\/s11139-012-9422-6","journal-title":"Ramanujan J."},{"issue":"1","key":"507_CR27","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1080\/23799927.2019.1566275","volume":"4","author":"Z Sun","year":"2019","unstructured":"Sun, Z., Winterhof, A.: 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(1), 30\u201336 (2019). https:\/\/doi.org\/10.1080\/23799927.2019.1566275","journal-title":"Int. J. Comput. Math. Comput. Syst. Theory"},{"issue":"2","key":"507_CR28","doi-asserted-by":"publisher","first-page":"33","DOI":"10.2478\/udt-2019-0012","volume":"14","author":"Z Sun","year":"2019","unstructured":"Sun, Z., Winterhof, A.: On the maximum order complexity of the Thue-Morse and Rudin-Shapiro sequence. Unif. Distrib. Theory 14(2), 33\u201342 (2019)","journal-title":"Unif. Distrib. Theory"},{"issue":"3","key":"507_CR29","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/s12095-019-00396-0","volume":"12","author":"Z Sun","year":"2020","unstructured":"Sun, Z., Zeng, X., Lin, D.: On the N th maximum order complexity and the expansion complexity of a Rudin-Shapiro-like sequence. Cryptogr. Commun. 12(3), 415\u2013426 (2020). https:\/\/doi.org\/10.1007\/s12095-019-00396-0","journal-title":"Cryptogr. Commun."},{"key":"507_CR30","unstructured":"Thue, A.: \u00dcber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Skrifter udgivne af Videnskabsselskabet i Christiania. 1, Math.Nat.wiss.Kl.1912,1 Jacob Dybwad (1912)"},{"key":"507_CR31","doi-asserted-by":"publisher","unstructured":"Topuzo\u011flu, A., Winterhof, A.: Pseudorandom sequences Topics in geometry, coding theory and cryptography. Springer, Dordrecht, https:\/\/doi.org\/10.1007\/1-4020-5334-4_4, vol. 6, pp 135\u2013166 (2007)","DOI":"10.1007\/1-4020-5334-4_4"},{"key":"507_CR32","first-page":"179","volume":"41","author":"E Zeckendorf","year":"1972","unstructured":"Zeckendorf, E.: Repr\u00e9sentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. Roy. Sci. Li\u00e8,ge 41, 179\u2013182 (1972)","journal-title":"Bull. Soc. Roy. Sci. Li\u00e8,ge"}],"container-title":["Cryptography and Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-021-00507-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12095-021-00507-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-021-00507-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T02:49:45Z","timestamp":1672714185000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12095-021-00507-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,7]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["507"],"URL":"https:\/\/doi.org\/10.1007\/s12095-021-00507-w","relation":{},"ISSN":["1936-2447","1936-2455"],"issn-type":[{"type":"print","value":"1936-2447"},{"type":"electronic","value":"1936-2455"}],"subject":[],"published":{"date-parts":[[2021,7,7]]},"assertion":[{"value":"18 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of Interests"}}]}}