On the stability of m-sequences

Alex J. Burrage, Ana Sǎlǎgean, Raphael C.W. Phan

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


We study the stability of m-sequences in the sense of determining the number of errors needed for decreasing the period of the sequences, as well as giving lower bounds on the k-error linear complexity of the sequences. For prime periods the results are straightforward so we concentrate on composite periods. We give exact results for the case when the period is reduced by a factor which is a Mersenne number and for the case when it is reduced by a prime p such that the order of 2 modulo p equals p - 1. The general case is believed to be difficult due to its similarity to a well studied problem in coding theory. We also provide results about the relative frequencies of the different cases. We formulate a conjecture regarding the minimum number of errors needed for reducing the period at all. Finally we apply our results to the LFSR components of several well known stream ciphers.

Original languageEnglish
Title of host publicationCryptography and Coding - 13th IMA International Conference, IMACC 2011, Proceedings
Number of pages16
Publication statusPublished - 2011
Externally publishedYes
EventIMA International Conference on Cryptography and Coding 2011 - Oxford, United Kingdom
Duration: 12 Dec 201115 Dec 2011
Conference number: 13th
https://link.springer.com/book/10.1007/978-3-642-25516-8 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7089 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceIMA International Conference on Cryptography and Coding 2011
Abbreviated titleIMACC 2011
Country/TerritoryUnited Kingdom
Internet address

Cite this