Cryptology ePrint Archive: Report 2014/686

The Adjacency Graph of Some LFSRs

Ming Li and Dongdai Lin

Abstract: In this paper, we discuss the adjacency graph of feedback shift registers (FSRs) whose characteristic polynomial can be written as $g=(x_0+x_1)*f$ for some linear function $f$. For $f$ contains an odd number of terms, we present a method to calculate the adjacency graph of FSR$_{(x_0+x_1)*f}$ from the adjacency graph of FSR$_f$. The parity of the weight of cycles in FSR$_{(x_0+x_1)*f}$ can also be determined easily. For $f$ contains an even number of terms, the theory is not so much complete. We need more information than the adjacency graph of FSR$_f$ to determine the adjacency graph of FSR$_{(x_0+x_1)*f}$. Besides, some properties about the cycle structure of linear feedback shift registers (LFSR) are presented.

Category / Keywords: secret-key cryptography / adjacency graph, LFSR

Date: received 2 Sep 2014

Contact author: liming at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20140902:073641 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]