Abstract
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 language | English |
---|---|
Title of host publication | Cryptography and Coding - 14th IMA International Conference, IMACC 2013, Proceedings |
Publisher | Springer-Verlag London Ltd. |
Pages | 16-27 |
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/978-3-642-45239-0 (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) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
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
- m-sequences