**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.

**Category / Keywords: **secret-key cryptography / feedback shift register, adjacency graph, De Bruijn sequence

**Date: **received 10 Mar 2016

**Contact author: **liming at iie ac cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20160310:181138 (All versions of this report)

**Short URL: **ia.cr/2016/269

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]