Cryptographically Strong de Bruijn Sequences with Large Periods

摘要

In this paper we first refine Mykkeltveit et al.'s technique for producing de Bruijn sequences through compositions. We then conduct an analysis on an approximation of the feedback functions that generate de Bruijn sequences. The cycle structures of the approximated feedback functions and the linear complexity of a sequence produced by an approximated feedback function are determined. Furthermore, we present a compact representation of an (n + 16)-stage nonlinear feedback shift register (NLFSR) and a few examples of de Bruijn sequences of period 2~n, 35 ≤ n ≤ 40, which are generated by the recursively constructed NLFSR together with the evaluation of their implementation.