CLR cover

Problem 148: Linearly generated words and primitive polynomials

\( \)

We consider sequences of length-$n$ binary non-unary words (each containing at least one nonzero bit). There are $N=2^n-1$ such words. By $\oplus$ denote operation xor on bits. Let $\alpha=(a_0,a_1,\ldots,a_{n-1})$ be a (control) sequence of bits. The LFSR-sequence associated with $\alpha$, denoted by $\LFSR(\alpha)$, is the sequence $b_1b_2b_3\cdots b_{N+n-1}$ of bits, such that for $n \lt k \lt N+n-2$. \[b_1b_2\cdots b_n\, = \, 0^{n-1}1,\] \[ b_{k+1}\, =\,a_0\cdot b_{k-n+1}\, \oplus\, a_1\cdot b_{k-n+2}\, \oplus\, a_2\cdot b_{k-n+3} \, \oplus \, \cdots \, \oplus\, a_{n-1}\cdot b_{k} \]

We fix the starting prefix $0^{n-1}1$ for simplicity. Observe that $N+n-2$ is the smallest length of a binary sequence containing each length-$n$ nonzero word. Denote by $\GEN(\alpha)$ the sequences of consecutive length-$n$ factors in $\LFSR(\alpha)$. Observe that $\GEN(\alpha)$ is of length $N$.

The polynomial related to $\LFSR(\alpha)$, where $\alpha=a_0a_1\cdots a_{n-1}$ is $$W_{\alpha}\,=\,x^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\cdots+a_1x^1+a_0$$ $W_{\alpha}$ is called a generating polynomial for $\LFSR(\alpha)$. If all words in $\GEN(\alpha)$ are different then the sequence $\LFSR(\alpha)$ is called a {\it PN sequence} (pseudo-noise) sequence. The polynomial $P$ is called {\it primitive} if all polynomials $x^i \ \mbox{mod}\ P(x)$ are distinct, for $1\le i \le 2^n-1$ (it is maximal number of nonzero binary polynomials of degree smaller than $n$). It is known, and surprising, that $\LFSR$-sequences corresponding to primitive polynomials are PN-sequences. In this way construction of PN sequences is reduced to construction of primitive polynomials, which is easier since one can use algebraic tools.

Compute the $m$-th word of $\GEN(\alpha)$ in $O(n^3\log m)$ time.

Improve time complexity of computing the $m$-th word of $\GEN(\alpha)$ to $O(n\log n\cdot \log m+n^2)$ time.