This blog post is about De Bruijn sequences and its relationship to cryptography. We focus here on De Bruijn sequences over the alphabet $A=\{0,1\}$.
Definition [De Bruijn sequence (binary)]. A binary string of length $2^n$ is called a De Bruijn sequence of order $n$ if each possible $n$-bit string occurs exactly once (incl. wrap-around) as a substring.
|
Picture 1 - DeBruijn graph for n=3 |
De Bruijn sequences are the shortest possible bitstring that contains all possible $n$-bit substrings. For each $n$ there are $$\frac{2^{2^{n-1}}}{2^n}$$ possible De Bruijn sequences. For example, a De Bruijn sequence of order $n=3$ is $$00011101$$ and of order $n=4$ is $$0000101100111101$$ There are several ways to create De Bruijn sequences. One way is walk along an
Hamiltonian Cycle in the corresponding
De Bruijn graph (see Picture 1)
. A De Bruijn graph is a directed graph of degree $2$ which has $2^n$ vertices. There is an edge from vertex $i$ to the two vertices $$(2i\;\text{mod}\:2^{n-1})\;\text{and}\;(2i\;\text{mod}\;2^{n-1})+1$$ The example sequence above for $n=3$ can be obtained by visiting the vertices in the graph from Picture 1 in the following order: $0,1,3,7,6,5,2,4,(0)$. Another way to create De Bruijn sequences is to use a
Linear Feedback Shift Register (LFSR), loaded with a primitive polynomial of degree $n$ to create a $m$-sequence. $m$-sequences are De Bruijn sequences that miss the substring $0_n$, i.e., the substring that consists of $n$ zeros (sometimes also called a
punctured De Bruijn sequence). There is also a relationship between discrete logarithms in GF$(2^n)$ and $m$-sequences which however is not the relationship i want to cover here. A good point to start reading about this topic is the book
Algebraic Shift Registers Sequences from Goresky and Klapper [1].