International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 06 November 2015

Ming Li, Mingxing Wang, Dongdai Lin
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.