Top

Cryptography and Communications

Published in:

13-09-2019

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

Authors: Zhimin Sun, Xiangyong Zeng, Da Lin

Published in: Cryptography and Communications | Issue 3/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Decimated m-sequences families with optimal partial Hamming correlation

next article On three conjectures of binary sequences with low odd-periodic autocorrelation

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Allouche, J.P., sequences, J. Shallit.: Automatic Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)CrossRef

Allouche, J.P., Liardet, P.: Generalized Rudin-Shapiro sequences. Acta Arithmet LX.1, 1–27 (1991)MathSciNetCrossRef

Allouche, J.P.: On a Golay-Shapiro-like sequence. Unif. Distrib. Theory 11(2), 205–210 (2016)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

Chan, L., Grimm, U.: Spectrum of a Rudin-Shapiro-like sequence. Adv. Appl. Math. 87, 16–23 (2017)MathSciNetCrossRef

Diem, C.: On the use of expansion series for stream ciphers. LMS J. Comput. Math. 15, 326–340 (2012)MathSciNetCrossRef

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.: 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)

Lafrance, P., Rampersad, N., Yee, R.: Some properties of a Rudin-Shapiro-like sequence. Adv. Appl. Math. 63, 19–40 (2015)MathSciNetCrossRef

10.

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.

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.

Mérai, L., Winterhof, A.: On the N th linear complexity of automatic sequences. J. Number Theory 187, 415–429 (2018)MathSciNetCrossRef

13.

Müllner, C.: The Rudin-Shapiro sequence and similar sequences are normal along squares. Can. J. Math. 70(5), 1096–1129 (2018)MathSciNetCrossRef

14.

Sun, Z., Winterhof, A.: On the maximum order complexity of the Thue-Morse sequence and the Rudin-Shapiro sequence. Preprint (2017)

15.

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.

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

Title: On the Nth maximum order complexity and the expansion complexity of a Rudin-Shapiro-like sequence
Authors: Zhimin Sun
Xiangyong Zeng
Da Lin
Publication date: 13-09-2019
Publisher: Springer US
Published in: Cryptography and Communications / Issue 3/2020
Print ISSN: 1936-2447
Electronic ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-019-00396-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2020

Properties of tight frames that are regular schemes

Editorial: Special issue on sequences and their applications 2018

Binary and ternary sequences with a few cross correlations

Frequency-hopping sequence sets with no-hit-zone through Cartesian product

On generalized hyper-bent functions

Two constructions for 16-QAM complementary sequence sets with non-power-of-two length

Premium Partner