Paper 2015/1091

Construction for de Bruijn Sequences with Large Orders

Junwu Dong and Dingyi Pei

Abstract

Sequences generated by maximum-period nonlinear feedback shift registers are known as de Bruijn sequences. The problem of designing de Bruijn sequences has received considerable attention. There is only one full cycle in the state graph of de Bruijn sequences. Most popular algorithms for generating de Bruijn sequences start from a nonsingular linear feedback shift register producing several shorter cycles in its state graph, then join them into one cycle. Unfortunately, the order $n$ of the resulting de Bruijn sequence by using this kind of algorithms is small so far (usually $n \le 40$). We introduce a new concept of correlated cycles between the cycles in the state graph of a LFSR. Based on this concept we present a algorithm for constructing de Bruijn sequences with large orders (such as $n=128$). This is the first publication for designing de Bruijn sequences with such large orders.

Metadata
Available format(s)
-- withdrawn --
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
de Bruijn sequencestate cycleperiod of irreducible polynomialconjugate states$t$-correlated circles
Contact author(s)
djunwu @ 163 com
History
2016-04-28: withdrawn
2015-11-10: received
See all versions
Short URL
https://ia.cr/2015/1091
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.