CLR cover
Previous problem

Problem 148: Linearly generated words and primitive polynomials

Next problem
\( \)

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 PN sequence (pseudo-noise) sequence. The polynomial $P$ is called 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 using matrix multiplications.

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