Cryptology ePrint Archive: Report 2015/1079

De Bruijn Sequences from Symmetric Shift Registers

Ming Li and Mingxing Wang and Dongdai Lin

Abstract: We consider the symmetric Feedback Shift Registers (FSRs), especially a special class of symmetric FSRs (we call them scattered symmetric FSRs), and construct a large class of De Bruijn sequences from them. It is shown that, at least O(2^((n-6)(logn)/2)) De Bruijn sequences of order n can be constructed from just one n-stage scattered symmetric FSR. To generate the next bit in the De Bruijn sequence from the current state, it requires no more than 2n comparisons and n+1 FSR shifts. By further analyse the cycle structure of the scattered symmetric FSRs, other methods for constructing De Bruijn sequences are suggested.

Category / Keywords: secret-key cryptography / symmetric Boolean function, feedback shift register, De Bruijn sequence, cycle joining method.

Date: received 5 Nov 2015, last revised 6 Nov 2015

Contact author: liming at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20151106:093244 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]