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: ia.cr/2015/1079
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]