{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T20:51:43Z","timestamp":1772052703072,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T00:00:00Z","timestamp":1636934400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T00:00:00Z","timestamp":1636934400000},"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":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce <jats:italic>rational complexity<\/jats:italic>, a new complexity measure for binary sequences. The sequence <jats:italic>s<\/jats:italic> \u2208 <jats:italic>B<\/jats:italic><jats:sup><jats:italic>\u03c9<\/jats:italic><\/jats:sup> is considered as binary expansion of a real fraction <jats:inline-formula><jats:alternatives><jats:tex-math>$s \\equiv {\\sum }_{k\\in \\mathbb {N}}s_{k}2^{-k}\\in [0,1] \\subset \\mathbb {R}$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>s<\/mml:mi>\n                  <mml:mo>\u2261<\/mml:mo>\n                  <mml:msub>\n                    <mml:mrow>\n                      <mml:mo>\u2211<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>\u2208<\/mml:mo>\n                      <mml:mi>\u2115<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                  <mml:msub>\n                    <mml:mrow>\n                      <mml:mi>s<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mo>\u2212<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                  <mml:mo>\u2208<\/mml:mo>\n                  <mml:mo>[<\/mml:mo>\n                  <mml:mn>0<\/mml:mn>\n                  <mml:mo>,<\/mml:mo>\n                  <mml:mn>1<\/mml:mn>\n                  <mml:mo>]<\/mml:mo>\n                  <mml:mo>\u2282<\/mml:mo>\n                  <mml:mi>\u211d<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We compute its continued fraction expansion (CFE) by the <jats:italic>Binary CFE Algorithm<\/jats:italic>, a bitwise approximation of <jats:italic>s<\/jats:italic> by binary search in the encoding space of partial denominators, obtaining rational approximations <jats:italic>r<\/jats:italic> of <jats:italic>s<\/jats:italic> with <jats:italic>r<\/jats:italic> \u2192 <jats:italic>s<\/jats:italic>. We introduce <jats:italic>Feedback in<\/jats:italic><jats:inline-formula><jats:alternatives><jats:tex-math>$\\mathbb {Q}$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u211a<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula><jats:italic>Shift Registers<\/jats:italic> (F<jats:inline-formula><jats:alternatives><jats:tex-math>$\\mathbb {Q}$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u211a<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>SRs) as the analogue of Linear Feedback Shift Registers (LFSRs) for the linear complexity L, and Feedback with Carry Shift Registers (FCSRs) for the 2-adic complexity A. We show that there is a substantial subset of prefixes with \u201ctypical\u201d linear and 2-adic complexities, around <jats:italic>n<\/jats:italic>\/2, but low rational complexity. Thus the three complexities sort out different sequences as non-random.<\/jats:p>","DOI":"10.1007\/s12095-021-00539-2","type":"journal-article","created":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T13:02:40Z","timestamp":1636981360000},"page":"433-457","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Rational complexity of binary sequences, F$\\mathbb {Q}$SRs, and pseudo-ultrametric continued fractions in $\\mathbb {R}$"],"prefix":"10.1007","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6094-1334","authenticated-orcid":false,"given":"Michael","family":"Vielhaber","sequence":"first","affiliation":[]},{"given":"M\u00f3nica del Pilar","family":"Canales Chac\u00f3n","sequence":"additional","affiliation":[]},{"given":"Sergio","family":"Jara Ceballos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,15]]},"reference":[{"key":"539_CR1","unstructured":"Berlekamp, E.: Non-binary BCH decoding. TR North Carolina State University Department of Statistics (1966)"},{"issue":"2","key":"539_CR2","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1109\/18.556111","volume":"43","author":"S Blackburn","year":"1997","unstructured":"Blackburn, S.: Fast rational interpolation, Reed-Solomon decoding, and the linear complexity profiles of sequences. IEEE Trans. IT 43(2), 537\u2013548 (1997)","journal-title":"IEEE Trans. IT"},{"issue":"3","key":"539_CR3","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":"539_CR4","doi-asserted-by":"crossref","unstructured":"Hu, H., Feng, D.: On the 2-adic complexity and the k-error 2-adic complexity of periodic binary sequences. In: SETA 2004 LNCS, vol. 3486, pp 185\u2013197 (2005)","DOI":"10.1007\/11423461_12"},{"key":"539_CR5","first-page":"361","volume":"1","author":"A Khintchine","year":"1935","unstructured":"Khintchine, A.: Metrische kettenbruchprobleme. Comput. Math. 1, 361\u2013382 (1935)","journal-title":"Comput. Math."},{"key":"539_CR6","doi-asserted-by":"crossref","unstructured":"Klapper, A., Goresky, M.: 2-Adic shift registers. In: Crypto \u201995 LNCS, vol. 963, pp 262\u2013273 (1995)","DOI":"10.1007\/3-540-44750-4_21"},{"key":"539_CR7","doi-asserted-by":"crossref","unstructured":"Klapper, A., Goresky, M.: Cryptanalysis based on 2-Adic rational approximation. In: Crypto \u201995, LNCS, vol. 963, pp 262\u2013273 (1995)","DOI":"10.1007\/3-540-44750-4_21"},{"key":"539_CR8","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":"539_CR9","first-page":"83","volume":"6","author":"RO Kuzmin","year":"1928","unstructured":"Kuzmin, R. O.: Sur une probl\u00e8me de Gauss. Atti Congr. Int. Bologna 6, 83\u201389 (1928)","journal-title":"Atti Congr. Int. Bologna"},{"key":"539_CR10","first-page":"178","volume":"57","author":"P L\u00e9vy","year":"1929","unstructured":"L\u00e9vy, P.: Sur les lois de probabilit\u00e9 dont d\u00e9pendent les quotients complets et incomplets d\u2019une fraction continue. Bull. S.M.F. 57, 178\u2013194 (1929)","journal-title":"Bull. S.M.F."},{"issue":"1","key":"539_CR11","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"},{"key":"539_CR12","doi-asserted-by":"crossref","unstructured":"Moree, P.: Artin\u2019s primitive root conjecture\u2014a survey. arXiv Math arXiv:0412262 (2012)","DOI":"10.1515\/integers-2012-0043"},{"issue":"2","key":"539_CR13","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"},{"key":"539_CR14","doi-asserted-by":"crossref","unstructured":"Perron, O.: Die Lehre von den Kettenbr\u00fcchen, Bd. I. Teubner, Stuttgart 1954\/1977","DOI":"10.1007\/978-3-663-12289-0"},{"key":"539_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-82865-2","volume-title":"Analysis and Design of Stream Ciphers","author":"R Rueppel","year":"1986","unstructured":"Rueppel, R.: Analysis and Design of Stream Ciphers. Springer, Berlin (1986)"},{"issue":"1","key":"539_CR16","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10623-009-9331-x","volume":"55","author":"T Tian","year":"2010","unstructured":"Tian, T., Qi, W.F.: Expected values for the rational complexity of finite binary sequences. Des. Codes Crypt. 55(1), 65\u201379 (2010)","journal-title":"Des. Codes Crypt."},{"issue":"2","key":"539_CR17","doi-asserted-by":"publisher","first-page":"531","DOI":"10.5802\/jtnb.296","volume":"12","author":"B Vall\u00e9e","year":"2000","unstructured":"Vall\u00e9e, B.: Digits and continuants in euclidean algorithms Ergodic versus tauberian theorems. J. Th\u00e9or. Nombres Bordeaux 12(2), 531\u2013570 (2000)","journal-title":"J. Th\u00e9or. Nombres Bordeaux"},{"key":"539_CR18","unstructured":"Vepstas, L.: The Minkowsi Question Mark, PSL(2,z) and the Modular Group http:\/\/ns.linas.org\/math\/chap-minkowski.pdf (2020)"},{"issue":"11","key":"539_CR19","doi-asserted-by":"publisher","first-page":"4383","DOI":"10.1109\/TIT.2007.907499","volume":"53","author":"M Vielhaber","year":"2007","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\u20134391 (2007). Preprint: https:\/\/arxiv.org\/pdf\/cs\/0511089.pdf","journal-title":"IEEE Trans. IT"},{"key":"539_CR20","doi-asserted-by":"crossref","unstructured":"Vielhaber, M.: A unified view on sequence complexity measures as isometries. In: SETA 2004 LNCS, vol. 3486, pp 143\u2013153 (2005)","DOI":"10.1007\/11423461_8"},{"key":"539_CR21","doi-asserted-by":"crossref","unstructured":"Vielhaber, M.: Reduce-by-feedback: timing resistant and DPA-aware modular multiplication, plus: how to break RSA by DPA. In: CHES 2012. Springer (2012)","DOI":"10.1007\/978-3-642-33027-8_27"},{"key":"539_CR22","unstructured":"Vielhaber, M.: V Tree\u2014continued fraction expansion, Stern-Brocot tree. Minkowski\u2019s ?(x) Function In Binary: Exponentially Faster. arXiv:2008.08020 (2020)"}],"container-title":["Cryptography and Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-021-00539-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12095-021-00539-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-021-00539-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T07:16:49Z","timestamp":1646291809000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12095-021-00539-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,15]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["539"],"URL":"https:\/\/doi.org\/10.1007\/s12095-021-00539-2","relation":{},"ISSN":["1936-2447","1936-2455"],"issn-type":[{"value":"1936-2447","type":"print"},{"value":"1936-2455","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,15]]},"assertion":[{"value":"28 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}