Construction of de Bruijn Sequences from Product of Two Irreducible Polynomials

Zuling Chang, Martianus Frederic Ezerman, San Ling, Huaxiong Wang

Abstract

De Bruijn sequences are fundamental components in cryptography, coding theory, and communications. While the Cycle Joining (CJ) method is a standard approach for constructing these sequences, its application to complex reducible polynomials has historically been computationally expensive. This paper presents a systematic framework for generating binary de Bruijn sequences using Linear Feedback Shift Registers (LFSRs) with characteristic polynomials formed by the product of two distinct irreducible polynomials, $f(x) = p(x)q(x)$. By introducing an efficient algorithm to identify conjugate pairs and leveraging the BEST theorem, the authors demonstrate a method to construct and count a vast number of unique sequences with significantly reduced computational overhead.

Introduction

A binary de Bruijn sequence of order $n$ is a cyclic sequence of length $2^n$ in which every possible $n$-bit string appears exactly once as a window. These sequences are highly valued for their properties of balance and complexity. However, as $n$ increases, the number of possible de Bruijn sequences grows at a rate of $2^{2^{n-1}-n}$, making their exhaustive generation impossible.

The most effective construction technique is the Cycle Joining (CJ) method. This approach starts with a Feedback Shift Register (FSR) that partitions the state space into several disjoint cycles. By identifying "conjugate pairs"—two states that differ only in their first bit—one can "bridge" these cycles, eventually merging them into a single Hamiltonian cycle of length $2^n$. While this process is well-documented for primitive polynomials, this research expands the methodology to polynomials of the form $f(x) = p(x)q(x)$, where $p$ and $q$ are distinct irreducible polynomials.

Methodology

Cycle Structure Analysis

The authors first analyze the algebraic structure of the state space produced by an LFSR with a reducible characteristic polynomial. For $f(x) = p(x)q(x)$, the state space is partitioned into disjoint cycles whose lengths are determined by the periods of $p(x)$ and $q(x)$. Understanding this partition is critical for determining how many cycles must be joined to form a complete de Bruijn sequence.

Adjacency Graph Construction

To visualize and manage the joining process, the authors utilize an adjacency graph. In this graph:

  • Each vertex represents a disjoint cycle produced by the LFSR.
  • An edge exists between two vertices if the corresponding cycles share at least one conjugate pair.

A spanning tree of this adjacency graph defines a set of bridges that, when applied to the LFSR, merge all cycles into a single de Bruijn sequence.

Algorithm 1: Efficient Bridge Identification

The primary challenge in the CJ method is the identification of conjugate pairs. Traditional exhaustive search methods are computationally prohibitive for large $n$. The authors propose Algorithm 1, which utilizes a full-rank matrix $P$ to map states between the combined LFSR space and the individual component spaces of $p(x)$ and $q(x)$.

This mapping allows the search for conjugate pairs to be performed in the smaller component spaces. The complexity is reduced from approximately $(lcm(e_1, e_2))^2$ to $e_1^2 + e_2^2$ (where $e$ represents the period of the sequences), representing a massive speedup for high-order sequences.

Key Insights and Results

The Power of Reducibility

By moving beyond simple primitive polynomials, the authors significantly increase the diversity of available sequences. For example, at $n=4$, the proposed method can generate 2,880 distinct sequences, a substantial increase over more restrictive construction methods.

Exact Counting via the BEST Theorem

The paper employs a variant of the BEST (de Bruijn, Ehrenfest, Smith, and Tutte) theorem to calculate the number of unique de Bruijn sequences. By finding the number of spanning trees in the adjacency graph, the authors can provide exact counts or high-fidelity estimates. For a specific case involving $n=60$, the authors estimate the construction of approximately $2^{60.797}$ distinct sequences.

Cyclotomic Connections

A significant theoretical contribution is the link established between cyclotomic numbers and the number of conjugate pairs. This algebraic connection allows for closed-form expressions (Theorem 4) for the total number of sequences in specific cases, such as LFSRs with characteristic polynomials $(x^2 + x + 1)p(x)$.

Discussion and Future Work

While the method is highly effective for the product of two polynomials, the authors note that as the number of factors $s$ increases beyond two, the complexity of the adjacency graph grows significantly. This makes the calculation of the adjacency matrix cofactor—and thus the exact sequence count—more difficult.

Future research directions include investigating the auto- and cross-correlation properties of these sequences, which are vital for spread-spectrum communications and autonomous systems. Additionally, the authors suggest that these high-complexity sequences could find applications in emerging fields like DNA-based data storage, where sequence diversity and balance are paramount.

Summary updated

BibTeX
@article{chang2018construction,
  author = {Zuling Chang and Martianus Frederic Ezerman and San Ling and Huaxiong Wang},
  title = {{Construction of de Bruijn Sequences from Product of Two Irreducible Polynomials}},
  journal = {Cryptogr. Commun},
  year = {2018},
  doi = {10.1007/s12095-017-0219-8},
}
Figure