{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T20:51:39Z","timestamp":1772052699701,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T00:00:00Z","timestamp":1754870400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T00:00:00Z","timestamp":1754870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hochschule Bremerhaven"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cryptogr. Commun."],"published-print":{"date-parts":[[2026,1]]},"abstract":"Abstract<\/jats:title>\n \n We show that for all infinite sequences\n \n \n $$s\\in \\mathbb {F}_q^\\omega $$<\/jats:tex-math>\n \n \n s<\/mml:mi>\n \u2208<\/mml:mo>\n \n F<\/mml:mi>\n q<\/mml:mi>\n \u03c9<\/mml:mi>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , two properties are preserved under forward and backward application of the continued fraction operator\n K<\/jats:bold>\n (the modified Berlekamp-Massey Algorithm). The first preserved property is that if\n \n \n $${\\text {supp}}(s)\\subset [r]_n$$<\/jats:tex-math>\n \n \n supp<\/mml:mtext>\n \n (<\/mml:mo>\n s<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2282<\/mml:mo>\n \n \n [<\/mml:mo>\n r<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , that is, the positions of the nonzero elements of\n s<\/jats:italic>\n lie in a certain residue class modulo\n n<\/jats:italic>\n , then also\n \n \n $${\\text {supp}}(\\textbf{K}(s))\\subset [r]_n$$<\/jats:tex-math>\n \n \n supp<\/mml:mtext>\n \n (<\/mml:mo>\n K<\/mml:mi>\n \n (<\/mml:mo>\n s<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2282<\/mml:mo>\n \n \n [<\/mml:mo>\n r<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . The other property applies only to fields with characteristic two: if the sequence consists of symbol pairs\n \n \n $$(s_{2n-1},s_{2n}$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \n s<\/mml:mi>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n ,<\/mml:mo>\n \n s<\/mml:mi>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ) with\n \n \n $$s_{2n} = \\alpha s_{2n-1}$$<\/jats:tex-math>\n \n \n \n s<\/mml:mi>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n =<\/mml:mo>\n \u03b1<\/mml:mi>\n \n s<\/mml:mi>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for a fixed\n \n \n $$\\alpha \\in \\mathbb {F}_{2^k}$$<\/jats:tex-math>\n \n \n \u03b1<\/mml:mi>\n \u2208<\/mml:mo>\n \n F<\/mml:mi>\n \n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , for all\n \n \n $$n\\in \\mathbb {N}$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \u2208<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $$t:= \\textbf{K}(s)$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n :<\/mml:mo>\n =<\/mml:mo>\n K<\/mml:mi>\n (<\/mml:mo>\n s<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , then also\n \n \n $$t_{2n} = \\alpha t_{2n-1}$$<\/jats:tex-math>\n \n \n \n t<\/mml:mi>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n =<\/mml:mo>\n \u03b1<\/mml:mi>\n \n t<\/mml:mi>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for all\n \n \n $$n\\in \\mathbb {N}$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \u2208<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We furthermore determine all sets\n \n \n $$V\\subset \\mathbb {F}_q^m$$<\/jats:tex-math>\n \n \n V<\/mml:mi>\n \u2282<\/mml:mo>\n \n F<\/mml:mi>\n q<\/mml:mi>\n m<\/mml:mi>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n invariant under\n K<\/jats:bold>\n for certain finite fields, that is, for which\n \n \n $$\\textbf{K}:V^\\omega \\rightarrow V^\\omega $$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n :<\/mml:mo>\n \n V<\/mml:mi>\n \u03c9<\/mml:mi>\n <\/mml:msup>\n \u2192<\/mml:mo>\n \n V<\/mml:mi>\n \u03c9<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and conjecture that there are no others even in the general case. In the binary case,\n \n \n $$\\mathbb {F}_{2^k}$$<\/jats:tex-math>\n \n \n F<\/mml:mi>\n \n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , we apply the result to a certain binary tree associated with the isometry\u00a0\n K<\/jats:bold>\n .\n <\/jats:p>","DOI":"10.1007\/s12095-025-00833-3","type":"journal-article","created":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T10:50:03Z","timestamp":1754909403000},"page":"153-172","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Pattern sets for $$\\mathbb {F}_q$$-sequences invariant under the continued fraction operator K (the Berlekamp-Massey algorithm)"],"prefix":"10.1007","volume":"18","author":[{"given":"M\u00f3nica\u00a0del\u00a0P.","family":"Canales","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Jara\u00a0C.","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Vielhaber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,11]]},"reference":[{"key":"833_CR1","doi-asserted-by":"crossref","unstructured":"Allouche, J.P., Shallit, J.: Automatic sequences, CUP, (2003)","DOI":"10.1017\/CBO9780511546563"},{"key":"833_CR2","volume-title":"Non-binary BCH decoding","author":"E Berlekamp","year":"1966","unstructured":"Berlekamp, E.: Non-binary BCH decoding. TR North Carolina State University, Department of Statistics (1966)"},{"key":"833_CR3","unstructured":"Canales Chac\u00f3n, M.P., Vielhaber, M.: Structural and computational complexity of isometries and their shift commutators. Electronic colloquium\u00a0on computational complexity, ECCC TR04\u2013057, (2004)"},{"key":"833_CR4","doi-asserted-by":"crossref","unstructured":"Canales Chac\u00f3n, M.P., Jara Ceballos S., Vielhaber, M.: Two pattern properties of binary sequences invariant under the continued fraction operator\u00a0K (the Berlekamp-Massey Algorithm) SETA 2024, Colchester, (2024)","DOI":"10.1007\/s12095-025-00833-3"},{"key":"833_CR5","unstructured":"Carter, G.D.: Aspects of local linear complexity. PhD Thesis. Royal Holloway and Bedford New College, London, (1989)"},{"issue":"1","key":"833_CR6","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF02560313","volume":"4","author":"Z Dai","year":"1988","unstructured":"Dai, Z., Wan, Z.: A relationship between the Berlekamp-Massey and the Euclidean algorithms for LFSR synthesis. Acta Math. Sin. 4(1), 55\u201363 (1988)","journal-title":"Acta Math. Sin."},{"key":"833_CR7","doi-asserted-by":"crossref","unstructured":"Dai, Z., Zeng, K.: Continued fractions and the Berlekamp-Massey algorithm. Adv. Cryptol.\u2013AUSCRYPT\u201990, LNCS 453, 23\u201331 (1990)","DOI":"10.1007\/BFb0030347"},{"issue":"3","key":"833_CR8","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1109\/TIT.1987.1057299","volume":"33","author":"JL Dornstetter","year":"1987","unstructured":"Dornstetter, J.L.: On the equivalence between Berlekamp\u2019s and Euclid\u2019s algorithm. IEEE Trans IT 33(3), 428\u2013431 (1987)","journal-title":"IEEE Trans IT"},{"key":"833_CR9","doi-asserted-by":"crossref","unstructured":"Klapper, A., Goresky, M.: Cryptanalysis based on 2-adic rational approximation. Crypto \u201995, LNCS, 963, 262\u2013273 (1995)","DOI":"10.1007\/3-540-44750-4_21"},{"key":"833_CR10","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s001459900024","volume":"10","author":"A Klapper","year":"1997","unstructured":"Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory. J Crypt 10, 111\u2013147 (1997)","journal-title":"J Crypt"},{"key":"833_CR11","unstructured":"Lagrange, J.L.: Additions au m\u00e9moire sur la r\u00e9duction des equations num\u00e9riques. M\u00e9moires de l\u2019Acad\u00e9mie royale des sciences et belles-lettres (de Berlin) 24 (1770)"},{"key":"833_CR12","doi-asserted-by":"crossref","unstructured":"Lidl, R., Niederreiter, H.: Introduction to finite fields and their applications, CUP (1994)","DOI":"10.1017\/CBO9781139172769"},{"issue":"1","key":"833_CR13","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1109\/TIT.1969.1054260","volume":"15","author":"J Massey","year":"1969","unstructured":"Massey, J.: Shift-register synthesis and BCH decoding. IEEE Trans. IT 15(1), 122\u2013127 (1969)","journal-title":"IEEE Trans. IT"},{"issue":"2","key":"833_CR14","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002000050098","volume":"9","author":"H Niederreiter","year":"1998","unstructured":"Niederreiter, H., Vielhaber, M.: Simultaneous shifted continued fraction expansions in quadratic time. AAECC 9(2), 125\u2013138 (1998)","journal-title":"AAECC"},{"issue":"1\u20132","key":"833_CR15","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0304-3975(99)00067-5","volume":"226","author":"H Niederreiter","year":"1999","unstructured":"Niederreiter, H., Vielhaber, M.: An algorithm for shifted continued fraction expansions in parallel linear time. TCS 226(1\u20132), 93\u2013104 (1999)","journal-title":"TCS"},{"issue":"3","key":"833_CR16","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcom.1996.0014","volume":"12","author":"H Niederreiter","year":"1996","unstructured":"Niederreiter, H., Vielhaber, M.: Tree complexity and a doubly exponential gap between structured and random sequences. J. Complex. 12(3), 187\u2013198 (1996)","journal-title":"J. Complex."},{"key":"833_CR17","doi-asserted-by":"crossref","unstructured":"Perron, O.: Die Lehre von den Kettenbr\u00fcchen, Bd.\u00a0I. Teubner, Stuttgart (1954\/1977)","DOI":"10.1007\/978-3-663-01496-6"},{"key":"833_CR18","unstructured":"Vielhaber, M.: Kettenbr\u00fcche, Komplexit\u00e4tsma\u00dfe und die Zuf\u00e4lligkeit von Symbolfolgen. Dissertation, Universit\u00e4t Wien (1997)"},{"key":"833_CR19","doi-asserted-by":"crossref","unstructured":"Vielhaber, M.: A unified view on sequence complexity measures as isometries. SETA 2004, LNCS, 3486, 143-153 (2005)","DOI":"10.1007\/11423461_8"},{"key":"833_CR20","doi-asserted-by":"crossref","unstructured":"Vielhaber, M.: Continued fraction expansion as isometry - the law of the iterated logarithm for linear, Jump, and 2-adic complexity. IEEE Trans. IT, 53(11), 4383-4391 (2007) Preprint: arXiv:cs\/0511089","DOI":"10.1109\/TIT.2007.907499"},{"key":"833_CR21","unstructured":"Vielhaber, M.: V tree \u2014 continued fraction expansion, Stern-Brocot tree, Minkowski\u2019s $$?({\\bf x})$$ function in binary: Exponentially faster. (2020). arXiv:2008.08020"},{"key":"833_CR22","unstructured":"Vielhaber, M., Canales, M.P., Jara, S.: Feedback in $$\\mathbb{Q}$$ Shift Registers F $$\\mathbb{Q}$$ SR: Pseudo-ultrametric continued fractions in R. SETA (2020)"},{"issue":"2","key":"833_CR23","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s12095-021-00539-2","volume":"14","author":"M Vielhaber","year":"2022","unstructured":"Vielhaber, M., Canales, M.P., Jara, S.: Rational complexity of binary sequences, F$$\\mathbb{Q} $$SRs, and pseudo-ultrametric continued fractions in $$\\mathbb{R} $$. Crypt. Commun. 14(2), 433\u2013457 (2022)","journal-title":"Crypt. Commun."},{"key":"833_CR24","unstructured":"Wang, M.Z., Massey, J.: The characterization of all binary sequences with a perfect linear complexity profile. EUROCRYPT \u201986, Link\u00f6ping (1986)"}],"container-title":["Cryptography and Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-025-00833-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12095-025-00833-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-025-00833-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T09:20:00Z","timestamp":1772011200000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12095-025-00833-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,11]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["833"],"URL":"https:\/\/doi.org\/10.1007\/s12095-025-00833-3","relation":{},"ISSN":["1936-2447","1936-2455"],"issn-type":[{"value":"1936-2447","type":"print"},{"value":"1936-2455","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,11]]},"assertion":[{"value":"12 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2025","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Incorrect Open Access funding information has been corrected in the Funding Note.","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}]}}