Skip to main content
Erschienen in: Cryptography and Communications 3/2020

13.09.2019

On the Nth maximum order complexity and the expansion complexity of a Rudin-Shapiro-like sequence

verfasst von: Zhimin Sun, Xiangyong Zeng, Da Lin

Erschienen in: Cryptography and Communications | Ausgabe 3/2020

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Based on the parity of the number of occurrences of a pattern 10 as a scattered subsequence in the binary representation of integers, a Rudin-Shapiro-like sequence is defined by Lafrance, Rampersad and Yee. The N th maximum order complexity and the expansion complexity of this Rudin-Shapiro-like sequence are calculated in this paper.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Allouche, J.P., sequences, J. Shallit.: Automatic Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)CrossRef Allouche, J.P., sequences, J. Shallit.: Automatic Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)CrossRef
4.
Zurück zum Zitat Brillhart, J., Morton, P.: A case study in mathematical research: the Golay-Rudin-Shapiro sequence. Am. Math. Mon. 103(10), 854–869 (1996)MathSciNetCrossRef Brillhart, J., Morton, P.: A case study in mathematical research: the Golay-Rudin-Shapiro sequence. Am. Math. Mon. 103(10), 854–869 (1996)MathSciNetCrossRef
6.
7.
Zurück zum Zitat Jansen, C.J.A.: Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods. Ph.D.dissertation, Technical University of Delft, Delft (1989) Jansen, C.J.A.: Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods. Ph.D.dissertation, Technical University of Delft, Delft (1989)
8.
Zurück zum Zitat Jansen, C.J.A.: The Maximum Order Complexity of Sequence Ensembles. In: Davies, D.W. (ed.) Advances in Cryptology - EUROCRYPT ’91, Lect. Notes Comput. Sci., vol. 547, pp 153–159. Springer, Berlin (1991) Jansen, C.J.A.: The Maximum Order Complexity of Sequence Ensembles. In: Davies, D.W. (ed.) Advances in Cryptology - EUROCRYPT ’91, Lect. Notes Comput. Sci., vol. 547, pp 153–159. Springer, Berlin (1991)
9.
Zurück zum Zitat Lafrance, P., Rampersad, N., Yee, R.: Some properties of a Rudin-Shapiro-like sequence. Adv. Appl. Math. 63, 19–40 (2015)MathSciNetCrossRef Lafrance, P., Rampersad, N., Yee, R.: Some properties of a Rudin-Shapiro-like sequence. Adv. Appl. Math. 63, 19–40 (2015)MathSciNetCrossRef
10.
Zurück zum Zitat Mauduit, C., Sárközy, A.: On finite pseudorandom binary sequences II. The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction. J. Number Theory 73(2), 256–276 (1998)MathSciNetCrossRef Mauduit, C., Sárközy, A.: On finite pseudorandom binary sequences II. The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction. J. Number Theory 73(2), 256–276 (1998)MathSciNetCrossRef
11.
Zurück zum Zitat Mérai, L., Niederreiter, H., Winterhof, A.: Expansion complexity and linear complexity of sequences over finite fields. Cryptogr. Commun. 9, 501–509 (2017)MathSciNetCrossRef Mérai, L., Niederreiter, H., Winterhof, A.: Expansion complexity and linear complexity of sequences over finite fields. Cryptogr. Commun. 9, 501–509 (2017)MathSciNetCrossRef
12.
Zurück zum Zitat Mérai, L., Winterhof, A.: On the N th linear complexity of automatic sequences. J. Number Theory 187, 415–429 (2018)MathSciNetCrossRef Mérai, L., Winterhof, A.: On the N th linear complexity of automatic sequences. J. Number Theory 187, 415–429 (2018)MathSciNetCrossRef
13.
Zurück zum Zitat Müllner, C.: The Rudin-Shapiro sequence and similar sequences are normal along squares. Can. J. Math. 70(5), 1096–1129 (2018)MathSciNetCrossRef Müllner, C.: The Rudin-Shapiro sequence and similar sequences are normal along squares. Can. J. Math. 70(5), 1096–1129 (2018)MathSciNetCrossRef
14.
Zurück zum Zitat Sun, Z., Winterhof, A.: On the maximum order complexity of the Thue-Morse sequence and the Rudin-Shapiro sequence. Preprint (2017) Sun, Z., Winterhof, A.: On the maximum order complexity of the Thue-Morse sequence and the Rudin-Shapiro sequence. Preprint (2017)
15.
Zurück zum Zitat Sun, Z., Winterhof, A.: On the maximum order complexity of subsequences of the Thue-Morse sequence and the Rudin-Shapiro sequence along squares. Int. J. Comput. Math. Comput. Syst. Theory 4(1), 30–36 (2019)MathSciNetCrossRef Sun, Z., Winterhof, A.: On the maximum order complexity of subsequences of the Thue-Morse sequence and the Rudin-Shapiro sequence along squares. Int. J. Comput. Math. Comput. Syst. Theory 4(1), 30–36 (2019)MathSciNetCrossRef
16.
Zurück zum Zitat Xing, C.P., Lam, K.Y.: Sequence with almost perfect linear complexity profiles and curves over finite fields. IEEE Trans. Inf. Theory 45(4), 1267–1270 (1999)MathSciNetCrossRef Xing, C.P., Lam, K.Y.: Sequence with almost perfect linear complexity profiles and curves over finite fields. IEEE Trans. Inf. Theory 45(4), 1267–1270 (1999)MathSciNetCrossRef
Metadaten
Titel
On the Nth maximum order complexity and the expansion complexity of a Rudin-Shapiro-like sequence
verfasst von
Zhimin Sun
Xiangyong Zeng
Da Lin
Publikationsdatum
13.09.2019
Verlag
Springer US
Erschienen in
Cryptography and Communications / Ausgabe 3/2020
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI
https://doi.org/10.1007/s12095-019-00396-0

Weitere Artikel der Ausgabe 3/2020

Cryptography and Communications 3/2020 Zur Ausgabe