**A Recursive Relation Between The Adjacency Graph of Some LFSRs and Its Applications**

*Ming Li and Dongdai Lin*

**Abstract: **In this paper, a general way to determine the adjacency graph of linear feedback shift registers (LFSRs) with characteristic polynomial (1+x)c(x) from the adjacency graph of LFSR with characteristic polynomial c(x) is discussed, where c(x) can be any polynomial. As an application, the adjacency graph of LFSRs with characteristic polynomial (1+x)^4p(x) are determined, where p(x) is a primitive polynomial. Besides, some properties about the cycles in LFSRs are presented.
The adjacency graph of LFSRs with characteristic polynomial (1+x)^mp(x) are also discussed.

**Category / Keywords: **adjacency graph, feedback shift register, de Bruijn sequences

**Date: **received 2 Sep 2014, last revised 18 Nov 2014

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

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

**Note: **Some applications are added. Some proofs are simplified.

**Version: **20141118:081827 (All versions of this report)

**Short URL: **ia.cr/2014/686

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

[ Cryptology ePrint archive ]