Efficient generation of elementary sequences

David Gardner, Ana Sǎlǎgean, Raphael C.W. Phan

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

2 Citations (Scopus)


Given an irreducible non-primitive polynomial g of degree n over we aim to compute in parallel all the elementary sequences with minimal polynomial g (i.e. one sequence from each class of equivalence under cyclic shifts). Moreover, they need to each be in a suitable phase such that interleaving them will produce an m-sequence with linear complexity deg(g); this m-sequence is therefore produced at the rate of q = (2 n - 1)/ord(g) bits per clock cycle. A naive method would use q LFSRs so our aim is to use considerably fewer. We explore two approaches: running a small number of Galois LFSRs with suitable seeds and using certain registers, possibly with a small amount of buffering; alternatively using only one (Galois or Fibonacci) LFSR and computing certain linear combinations of its registers. We ran experiments for all irreducible polynomials of degree n up to 14 and for each n we found that efficient methods exist for at least one m-sequence. A combination of the two approaches above is also described.

Original languageEnglish
Title of host publicationCryptography and Coding - 14th IMA International Conference, IMACC 2013, Proceedings
PublisherSpringer-Verlag London Ltd.
Number of pages12
ISBN (Print)9783642452383
Publication statusPublished - 2013
Externally publishedYes
EventIMA International Conference on Cryptography and Coding 2013 - Oxford, United Kingdom
Duration: 17 Dec 201319 Dec 2013
Conference number: 14th
https://link.springer.com/book/10.1007/978-3-642-45239-0 (Proceedings)

Publication series

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


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


  • elementary sequences
  • Fibonacci LFSR
  • Galois LFSR
  • interleaving
  • m-sequences

Cite this