Cryptology ePrint Archive: Report 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.

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:

[ Cryptology ePrint archive ]