International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 05 July 2015

Ming Li, Dongdai Lin
ePrint Report ePrint Report
We continue the research in \\cite{jans1991} to construct de Bruijn sequences from feedback shift registers (FSRs) that contains only very short cycles. Firstly, we suggest another way to define the representative of a cycle. Compared with the definition in \\cite{jans1991}, this definition can greatly improve the performance of the cycle joining algorithm. Then we construct a large class of nonlinear FSRs that contains only very short cycles. The length of the cycles in these $n$-stage FSRs are less than $2n$. Based on these FSRs, $O(2^{\\frac{n}{2}-\\mathrm{log} n})$ de Bruijn sequences of order $n$ are constructed. To generate the next bit in the de Bruijn sequence from the current state, it requires only $2n$ bits of storage and less than $2n$ FSR shifts.

Expand

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