# Convert m-Sequence into a de Bruijn Sequence

In his paper Alternating Step Generator Controlled by de Bruijn Sequence, C.G. Günther states on page three that

a de Bruijn sequence (..) can easily be obtained from an m-sequence (maximal length LFSR sequence)

Unfortunately he gives no method for doing this in the paper, and I have been unable to find such a method in my own research. Can anyone clue me in as to what Mr. Günther had in mind there? Is there an easy circuit for converting an m-sequence into a de Bruijn sequence?

• @fgrieu: My thinking is that Gunther is alluding to a shift register with some kind of nonlinear feedback function consisting of XOR gate(s) with some other nonlinear gate(s), AND, OR, some combination thereof. – William Hird Apr 8 '14 at 4:41
• I don't understand why Gunther says in the paper "it is easy to convert an m-sequence into a deBruijn sequence. To me easy means simple. If you read some of the papers on generating deBruijn sequences, the syntheses are very complicated!! – William Hird Apr 8 '14 at 5:20

A de Bruijn Sequence, as defined in N.G. de Bruijn's A combinatorial problem, Proc. K. Ned. Akad. Wet., vol. 49, pp 758-764, 1946 (with attribution to Ir. K. Posthumus) is

an ordered cycle of $2^n$ digits 0 or 1, such that the $2^n$ possible ordered sets of $n$ consecutive digits of that cycle are all different.

The example given for $n=3$ is the sequence 00010111, yielding sets 000, 001, 010, 101, 011, 111, 110, 100.

Given that, a de Bruijn Sequence of length $2^n$ is obtained from any m-sequence of length $2^n-1$ (that is, the cyclic output of a LFSR with a primitive polynomial of degree $n$ starting from a non-zero state) by inserting a single 0 in the single subsequence with $n-1$ consecutive 0.

Update per comment: We can implement a circuit that outputs a de Bruijn Sequence of length $2^n$ using $n$ D-type flip-flops connected as for a maximal-length Fibonnaci LFSR with $n$ stages, by adding an additional XOR term equal to the NOR of the outputs of the $n-1$ flip-flops on the feedback's side. In the following drawing (which outputs the example sequence above), the added gates are NOR1 and XOR2.

Note 0: When the number of stages $n$ gets large, the NOR gate with $n-1$ inputs gets annoying; one can trade this for a $\lceil\log_2(n)\rceil$-bit counter with reset, counting the number of consecutive zeroes in the output, giving a $1$ when reaching $n-1$ consecutive zeroes, and that output the additional XOR term.

Note 1: A de Bruijn generator is used in the paper only for the control generator of the ASG, deciding which of the other two are clocked. It would be questionable to also use a de Bruijn generator for any of the other two generators: notice that if the control generator has $c$ bits, a slave generator $x$ bits, and both are de Bruijn, the overall period of the slave's output is $2^{\max(c,x+1)}$, rather than $2^c\cdot(2^x-1)$ when the slave is a maximal-length LFSR.

Note 2: I do not see why the ASG's security would be weakened if the control generator was a maximal-length LFSR rather than a de Bruijn generator, with both slaves maximal-length LFSRs, provided $\gcd(2^{c-1}-1,2^x-1)$ is small [as well as $\gcd(2^x-1,2^y-1)$], where $c$ (resp. $x$, $y$) are the number of bits of the control generator (resp. the slave generator clocked when the control generator outputs $0$, the other slave generator). The original paper hints at another paper (submitted to IEEE Transactions on Information Theory, but I could not locate it) covering the case of maximal-length LFSR as control generator. It also seems to be the case in this article on the ASG, and some of its references.

Late addition: This is also easy in software. Assume $x^\mathtt n+x^\mathtt k+1$ is a primitive trinomial over $GF(2)$ (suitable constants $\mathtt n$ and $\mathtt k$ can be obtained from Jörg Arndt's Complete list of primitive trinomials over GF(2) up to degree 400). If x is an unsigned integer variable at least $\mathtt n$ bits wide, then the C expression
x = ((((x>>k)^x)&1)<<(n-1))|(x>>1);
readily implements a LFSR with period $2^\mathtt n-1$ (when starting from any positive x less than $2^\mathtt n$). We can change this to
x = ((((x>>k)^x^!(x>>1))&1)<<(n-1))|(x>>1);
which implements a NLFSR with period $2^\mathtt n$ (when starting from any non-negative x less than $2^\mathtt n$).

• A feedback function with a 62 input NOR gate is going to be way too slow for my purposes :-( – William Hird Apr 8 '14 at 18:00
• @William Hird: FOUR options: A) using a LFSR, see note 2; B) Just do it: with seventeen 4-inputs NOR gates and four 4-input NAND gates you make a 64-inputs NOR gate with only 3 of the lowest delays logic offers (perhaps 84 CMOS pairs); C) the counter trick of note 0, but its main purpose is to lower the transistor count when using MANY stages. Oh, BTW, 63 stages is not cryptographically strong, I'm afraid. D) Or get away of the ASG, use Trivium; its uses much less gates than the ASG, and has no long propagation delay. – fgrieu Apr 8 '14 at 19:06
• How about another solution? Make a generator consisting of three LFSR's , the outputs of which are XOR'd together , but each LFSR has its own LFSR as a random clock. Sure you will make the key length greater but the added clocking complexity will make attacks like the edit distance attack computationally infeasible. Who knows, maybe some clever mathematician will show that breaking this generator is NP Complete by showing a reduction to 3-SAT. ;-) – William Hird Apr 8 '14 at 20:44
• @William Hird: If you are ready to change algorithm, rather than venture in something new and untested, there's A5/1 with longer LFSRs, which borrows from the ASG, and remains quite simple to implement; and the three Profile 2 (HW) eSTREAM ciphers. Of these, I like Trivium, because it is flexible enough to be either a) compact and fast in hardware; b) very fast in hardware; c) reasonably fast in software. – fgrieu Apr 9 '14 at 7:07
• Thank you fgrieu but I am only interested in designing my own CSPRNG. I only study other designs to see what makes them strong (or fail !). It the reason I took up cryptography as a hobby. :-D – William Hird Apr 9 '14 at 17:49