Abstract
Given an irreducible nonprimitive 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 msequence with linear complexity deg(g); this msequence 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 msequence. A combination of the two approaches above is also described.
Original language  English 

Title of host publication  Cryptography and Coding  14th IMA International Conference, IMACC 2013, Proceedings 
Publisher  SpringerVerlag London Ltd. 
Pages  1627 
Number of pages  12 
ISBN (Print)  9783642452383 
DOIs  
Publication status  Published  2013 
Externally published  Yes 
Event  IMA International Conference on Cryptography and Coding 2013  Oxford, United Kingdom Duration: 17 Dec 2013 → 19 Dec 2013 Conference number: 14th https://link.springer.com/book/10.1007/9783642452390 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 

Volume  8308 LNCS 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  IMA International Conference on Cryptography and Coding 2013 

Abbreviated title  IMACC 2013 
Country/Territory  United Kingdom 
City  Oxford 
Period  17/12/13 → 19/12/13 
Internet address 

Keywords
 elementary sequences
 Fibonacci LFSR
 Galois LFSR
 interleaving
 msequences