Paper 2016/269
The Adjacency Graphs of Linear Feedback Shift Registers with Primitive-like Characteristic Polynomials
Ming Li and Dongdai Lin
Abstract
We consider the adjacency graphs of the linear feedback shift registers (LFSRs) with characteristic polynomials of the form l(x)p(x), where l(x) is a polynomial of small degree and p(x) is a primitive polynomial. It is shown that, their adjacency graphs are closely related to the association graph of l(x) and the cyclotomic numbers over finite fields. By using this connection, we give a unified method to determine their adjacency graphs. As an application of this method, we explicitly calculate the adjacency graphs of LFSRs with characteristic polynomials of the form (1+x+x^3+x^4)p(x), and construct a large class of De Bruijn sequences from them.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- feedback shift registeradjacency graphDe Bruijn sequence
- Contact author(s)
- liming @ iie ac cn
- History
- 2016-03-10: received
- Short URL
- https://ia.cr/2016/269
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/269,
author = {Ming Li and Dongdai Lin},
title = {The Adjacency Graphs of Linear Feedback Shift Registers with Primitive-like Characteristic Polynomials},
howpublished = {Cryptology {ePrint} Archive, Paper 2016/269},
year = {2016},
url = {https://eprint.iacr.org/2016/269}
}
