{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T05:49:48Z","timestamp":1761630588523},"publisher-location":"London","reference-count":36,"publisher":"Springer London","isbn-type":[{"type":"print","value":"9781852331962"},{"type":"electronic","value":"9781447105510"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/978-1-4471-0551-0_5","type":"book-chapter","created":{"date-parts":[[2011,8,26]],"date-time":"2011-08-26T08:46:19Z","timestamp":1314348379000},"page":"67-78","source":"Crossref","is-referenced-by-count":39,"title":["Some Computable Complexity Measures for Binary Sequences"],"prefix":"10.1007","author":[{"given":"Harald","family":"Niederreiter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"1702","DOI":"10.1109\/18.333898","volume":"40","author":"SR Blackburn","year":"1994","unstructured":"S.R. Blackburn, A generalisation of the discrete Fourier transform: determining the minimal polynomial of a periodic sequence, IEEE Trans. Inform. Theory\n                40 (1994), 1702\u20131704.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"5_CR2","volume-title":"\u201cApplications of Finite Fields\u201d","author":"SR Blackburn","year":"1996","unstructured":"S.R. Blackburn, A generalisation of the discrete Fourier transform, in \u201cApplications of Finite Fields\u201d (D. Gollmann, ed.), pp. 111\u2013116, Oxford University Press, Oxford, 1996."},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1109\/18.556111","volume":"43","author":"SR Blackburn","year":"1997","unstructured":"S.R. Blackburn, Fast rational interpolation, Reed-Solomon decoding, and the linear complexity profiles of sequences, IEEE Trans. Inform. Theory\n                43 (1997), 537\u2013548.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"5_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03049-3","volume-title":"\u201cInformation and Randomness: An Algorithmic Perspective\u201d","author":"C Calude","year":"1994","unstructured":"C. Calude, \u201cInformation and Randomness: An Algorithmic Perspective\u201d, Springer-Verlag, Berlin, 1994."},{"key":"5_CR5","doi-asserted-by":"crossref","first-page":"401","DOI":"10.24033\/bsmf.1926","volume":"108","author":"G Christol","year":"1980","unstructured":"G. Christol, T. Kamae, M. Mend\u00e8s France, and G. Rauzy, Suites alg\u00e9briques, automates et substitutions, Bull. Soc. Math. France\n                108 (1980), 401\u2013419.","journal-title":"Bull. Soc. Math. France"},{"key":"5_CR6","volume-title":"\u201cStream Ciphers and Number Theory\u201d","author":"TW Cusick","year":"1998","unstructured":"T.W. Cusick, C. Ding, and A. Renvall, \u201cStream Ciphers and Number Theory\u201d, Elsevier, Amsterdam, 1998."},{"key":"5_CR7","first-page":"24","volume-title":"\u201cAdvances in Cryptology \u2014 AUSCRYPT \u201880\u201d","author":"Z Dai","year":"1990","unstructured":"Z. Dai and K. Zeng, Continued fractions and the Berlekamp-Massey algorithm, in \u201cAdvances in Cryptology \u2014 AUSCRYPT \u201880\u201d (J. Seberry and J. Pieprzyk, eds.), Lecture Notes in Computer Science, Vol. 453, pp. 24\u201331, Springer-Verlag, Berlin, 1990."},{"key":"5_CR8","first-page":"130195","volume":"4","author":"M Dekking","year":"1983","unstructured":"M. Dekking, M. Mend\u00e8s France, and A. van der Poorten, FOLDS!, The Math. Intelligencer\n                4 (1983), 130\u2013138,173\u2013181,190\u2013195.","journal-title":"The Math. Intelligencer"},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science, Vol. 561","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54973-0","volume-title":"\u201cThe Stability Theory of Stream Ciphers\u201d","author":"C Ding","year":"1991","unstructured":"C. Ding, G. Xiao, and W. Shan, \u201cThe Stability Theory of Stream Ciphers\u201d, Lecture Notes in Computer Science, Vol. 561, Springer-Verlag, Berlin, 1991."},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1109\/TIT.1987.1057299","volume":"33","author":"J-L Dornstetter","year":"1987","unstructured":"J.-L. Dornstetter, On the equivalence between Berlekamp\u2019s and Euclid\u2019s algorithms, IEEE Trans. Inform. Theory\n                33 (1987), 428\u2013431.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1109\/TIT.1983.1056619","volume":"29","author":"RA Games","year":"1983","unstructured":"R.A. Games and A.H. Chan, A fast algorithm for determining the complexity of a binary sequence with period 272, IEEE Trans. Inform. Theory\n                29 (1983), 144\u2013146.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"5_CR12","volume-title":"\u201cInvestigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods\u201d","author":"CJA Jansen","year":"1989","unstructured":"C.J.A. Jansen, \u201cInvestigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods\u201d, Ph.D. Thesis, Technical University of Delft, 1989."},{"key":"5_CR13","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/3-540-46416-6_13","volume-title":"\u201cAdvances in Cryptology \u2014 EUROCRYPT \u201881\u201d","author":"CJA Jansen","year":"1991","unstructured":"C.J.A. Jansen, The maximum order complexity of sequence ensembles, in \u201cAdvances in Cryptology \u2014 EUROCRYPT \u201881\u201d (D.W. Davies, ed.), Lecture Notes in Computer Science, Vol. 547, pp. 153\u2013159, Springer-Verlag, Berlin, 1991."},{"key":"5_CR14","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/0-387-34805-0_10","volume-title":"\u201cAdvances in Cryptology \u2014 CRYPTO \u201889\u201d","author":"CJA Jansen","year":"1990","unstructured":"C.J.A. Jansen and D.E. Boekee, The shortest feedback shift register that can generate a given sequence, in \u201cAdvances in Cryptology \u2014 CRYPTO \u201889\u201d (G. Brassard, ed.), Lecture Notes in Computer Science, Vol. 435, pp. 90\u201399, Springer-Verlag, Berlin, 1990."},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/BFb0030372","volume-title":"\u201cAdvances in Cryptology \u2014 AUSCRYPT \u201880\u201d","author":"CJA Jansen","year":"1990","unstructured":"C.J.A. Jansen and D.E. Boekee, On the significance of the directed acyclic word graph in cryptology, in \u201cAdvances in Cryptology \u2014 AUSCRYPT \u201880\u201d (J. Seberry and J. Pieprzyk, eds.), Lecture Notes in Computer Science, Vol. 453, pp. 318\u2013326, Springer-Verlag, Berlin, 1990."},{"key":"5_CR16","unstructured":"T. Kaida, S. Uehara, and K. Imamura, A new algorithm for the k -error linear complexity of sequences over GF(p\n                \n                  m\n                \n                ) with period pn, this volume."},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/3-540-58108-1_21","volume-title":"\u201cFast Software Encryption\u201d","author":"A Klapper","year":"1994","unstructured":"A. Klapper and M. Goresky, 2-adic shift registers, in \u201cFast Software Encryption\u201d (R. Anderson, ed.), Lecture Notes in Computer Science, Vol. 809, pp. 174\u2013178, Springer-Verlag, Berlin, 1994."},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s001459900024","volume":"10","author":"A Klapper","year":"1997","unstructured":"A. Klapper and M. Goresky, Feedback shift registers, 2-adic span, and combiners with memory, J. Cryptology\n                10 (1997), 111\u2013147.","journal-title":"J. Cryptology"},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A Lempel","year":"1976","unstructured":"A. Lempel and J. Ziv, On the complexity of finite sequences, IEEE Trans. Inform. Theory\n                22 (1976), 75\u201381.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"5_CR20","volume-title":"\u201cFinite Fields\u201d, Addison-Wesley, Reading, MA, 1983; reprint","author":"R Lidl","year":"1997","unstructured":"R. Lidl and H. Niederreiter, \u201cFinite Fields\u201d, Addison-Wesley, Reading, MA, 1983; reprint, Cambridge University Press, Cambridge, 1997."},{"key":"5_CR21","first-page":"321","volume-title":"\u201cHandbook of Algebra\u201d","author":"R Lidl","year":"1996","unstructured":"R. Lidl and H. Niederreiter, Finite fields and their applications, in \u201cHandbook of Algebra\u201d (M. Hazewinkel, ed.), Vol. 1, pp. 321\u2013363, Elsevier, Amsterdam, 1996."},{"key":"5_CR22","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1090\/S0025-5718-1975-0369276-7","volume":"29","author":"WH Mills","year":"1975","unstructured":"W.H. Mills, Continued fractions and linear recurrences, Math. Comp. 29 (1975), 173\u2013180.","journal-title":"Math. Comp"},{"key":"5_CR23","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/3-540-46416-6_10","volume-title":"\u201cAdvances in Cryptology \u2014 EUROCRYPT \u201881\u201d","author":"S Mund","year":"1991","unstructured":"S. Mund, Ziv-Lempel complexity for periodic sequences and its cryptographic application, in \u201cAdvances in Cryptology \u2014 EUROCRYPT \u201881\u201d (D. W. Davies, ed.), Lecture Notes in Computer Science, Vol. 547, pp. 114\u2013126, Springer-Verlag, Berlin, 1991."},{"key":"5_CR24","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-39118-5_5","volume-title":"\u201cAdvances in Cryptology \u2014 EUROCRYPT \u201887\u201d","author":"H Niederreiter","year":"1988","unstructured":"H. Niederreiter, Sequences with almost perfect linear complexity profile, in \u201cAdvances in Cryptology \u2014 EUROCRYPT \u201887\u201d (D. Chaum and W.L. Price, eds.), Lecture Notes in Computer Science, Vol. 304, pp. 37\u201351, Springer-Verlag, Berlin, 1988."},{"key":"5_CR25","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/3-540-45961-8_17","volume-title":"\u201cAdvances in Cryptology \u2014 EUROCRYPT \u201888\u201d","author":"H Niederreiter","year":"1988","unstructured":"H. Niederreiter, The probabilistic theory of linear complexity, in \u201cAdvances in Cryptology \u2014 EUROCRYPT \u201888\u201d (C.G. G\u00fcnther, ed.), Lecture Notes in Computer Science, Vol. 330, pp. 191\u2013209, Springer-Verlag, Berlin, 1988."},{"key":"5_CR26","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/3-540-46885-4_50","volume-title":"\u201cAdvances in Cryptology \u2014 EUROCRYPT \u201889\u201d","author":"H Niederreiter","year":"1990","unstructured":"H. Niederreiter, Keystream sequences with a good linear complexity pro-file for every starting point, in \u201cAdvances in Cryptology \u2014 EUROCRYPT \u201889\u201d (J.-J. Quisquater and J. Vandewalle, eds.), Lecture Notes in Computer Science, Vol. 434, pp. 523\u2013532, Springer-Verlag, Berlin, 1990."},{"key":"5_CR27","first-page":"359","volume-title":"\u201cFinite Fields, Coding Theory, and Advances in Communications and Computing\u201d","author":"H Niederreiter","year":"1993","unstructured":"H. Niederreiter, Finite fields and cryptology, in \u201cFinite Fields, Coding Theory, and Advances in Communications and Computing\u201d (G.L. Mullen and P.J.-S. Shiue, eds.), pp. 359\u2013373, M. Dekker, New York, 1993."},{"key":"5_CR28","unstructured":"H. Niederreiter and H. Paschinger, Counting functions and expected values in the stability theory of stream ciphers, this volume."},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcom.1996.0014","volume":"12","author":"H Niederreiter","year":"1996","unstructured":"H. Niederreiter and M. Vielhaber, Tree complexity and a doubly exponential gap between structured and random sequences, J. Complexity\n                12 (1996), 187\u2013198.","journal-title":"J. Complexity"},{"key":"5_CR30","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002000050098","volume":"9","author":"H Niederreiter","year":"1998","unstructured":"H. Niederreiter and M. Vielhaber, Simultaneous shifted continued fraction expansions in quadratic time, Applicable Algebra Engrg. Comm. Comput. 9 (1998), 125\u2013138.","journal-title":"Applicable Algebra Engrg. Comm. Comput."},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"H. Niederreiter and M. Vielhaber, An algorithm for shifted continued fraction expansions in parallel linear time, Theoretical Computer Science,to appear.","DOI":"10.1016\/S0304-3975(99)00067-5"},{"key":"5_CR32","first-page":"564","volume":"104","author":"F Piper","year":"1987","unstructured":"F. Piper, Stream ciphers, Elektrotechnik and Maschinenbau\n                104 (1987), 564\u2013568.","journal-title":"Elektrotechnik and Maschinenbau"},{"key":"5_CR33","first-page":"65","volume-title":"\u201cContemporary Cryptology: The Science of Information Integrity\u201d","author":"RA Rueppel","year":"1992","unstructured":"R.A. Rueppel, Stream ciphers, in \u201cContemporary Cryptology: The Science of Information Integrity\u201d (G.J. Simmons, ed.), pp. 65\u2013134, IEEE Press, New York, 1992."},{"key":"5_CR34","doi-asserted-by":"publisher","first-page":"1398","DOI":"10.1109\/18.243455","volume":"39","author":"M Stamp","year":"1993","unstructured":"M. Stamp and C.F. Martin, An algorithm for the k-error linear complexity of binary sequences with period 2n, IEEE Trans. Inform. Theory\n                39 (1993), 1398\u20131401.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"5_CR35","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1109\/TIT.1979.1055987","volume":"25","author":"LR Welch","year":"1979","unstructured":"L.R. Welch and R.A. Scholtz, Continued fractions and Berlekamp\u2019s algorithm, IEEE Trans. Inform. Theory\n                25 (1979), 19\u201327.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"5_CR36","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J Ziv","year":"1977","unstructured":"J. Ziv and A. Lempel, A universal algorithm for sequential data compression, IEEE Trans. Inform. Theory\n                23 (1977), 337\u2013343.","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Sequences and their Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4471-0551-0_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:26:24Z","timestamp":1619828784000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4471-0551-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9781852331962","9781447105510"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-1-4471-0551-0_5","relation":{},"subject":[],"published":{"date-parts":[[1999]]}}}