Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?

Question

There's a classical method to efficiently test if a LFSR with $n$ bits is maximal-length (or equivalently, if the feedback polynomial is primitive), when the factorization of $2^n-1$ is available.

Do we have an efficient method working when that factorization is unavailable, e.g. because we do not want to depend on a full factorization algorithm, or on the factorizations of $2^n-1$ (for all $n<2991$, and some much higher $n$) amassed by the Cunningham Project?

---

For reference, the classical method goes:

1. Check that starting from a particular non-zero original state (e.g. the low-order bit set), and after stepping $2^n-1$ times, we get back to the original state; if not, the LFSR is not maximal-length (since it did not cycle after the maximum period $2^n-1$).
2. If $2^n-1$ is not prime, then for each of its prime divisors $p$
   • check that starting from the original state, and after stepping $(2^n-1)/p$ times, we do not get back to the original state; if we do, conclude that the LFSR is not maximal-length (since it cycled before the maximum period $2^n-1$).
3. Conclude that the LFSR is demonstrably maximal-length (since its period starting from the initial state is bound to be a divisor of $2^n-1$, and we checked a multiple of any divisor of $2^n-1$ other than itself in the previous step).

The algorithm is fast, because the linearity of the LFSR allows computing the state after $k$ steps in time $O(n^2\cdot\log_2k)$ and memory $O(n^2)$.

Answer 1

This is basically the problem of finding a generator $g$ in a group $G$ of order $2^n-1$, where the factorization of $2^n-1$ is unknown.

Here is a pragmatic solution that should work fine in practice. Use ECM factoring to find all small factors of $2^n-1$; in this way, find as many prime factors of $2^n-1$ as you can.

Now, pick $g$ uniformly at random. For each known prime divisor $p$ of $2^n-1$, test that $g^{(2^n-1)/p} \ne 1$. If this test holds for all known prime divisors $p$, then output $g$. Otherwise, go back to the beginning and pick a new $g$.

Of course, you can only do this test for the prime divisors that you know of, so in principle, there is some risk that that you were unlucky and accepted a $g$ that isn't actually a generator (because $g^{(2^n-1)/q}=1$ for some prime divisor $q$ that you didn't know of). The good news, though, is that the probability of this happening is exponentially small.

For instance, suppose we have found all prime divisors of 80 bits or less---something that ECM should easily be able to do. Then there can be at most 37 additional prime divisors of $2^{2991}-1$. The probability that $g$ happens to satisfy $g^{(2^n-1)/q}=1$ for a single one of them is $1/q$, i.e., $\le 1/2^{80}$. Therefore, by a union bound, the probability that $g$ happens to satisfy $g^{(2^n-1)/q}=1$ for any of those 37 prime divisors is $\le 37/2^{80} \le 1/2^{74}$, which is so small it can be safely ignored for all cryptographic purposes.

This assumes there is a good practical reason to want to find a maximal-length LFSR of length exactly 2991, something that sounds pretty dubious to me.

---

In particular, the algorithm I have in mind for choosing a maximal-length LFSR on $n$ bits is as follows:

1. Choose a random feedback polynomial, uniformly at random from the set of all monic polynomials of degree $n$. (As an optimization, make sure the constant term is $1$ and that the number of terms is odd; this will reduce the number of rejections in step 3.)

2. Choose a random non-zero starting state $S$.

3. Starting from $S$, step the LFSR forward $2^n-1$ times and check that you get back to $S$. If not, it is not maximal-length; go back to step 1.

4. For each known prime divisor $p$ of $2^n-1$: Starting from $S$, step the LFSR forward $(2^n-1)/p$ steps and check that you do not get back to the starting state. If you do get back to $S$, it is not maximal-length; go back to step 1.

5. Output the feedback polynomial; it is probably maximal-length.

This algorithm is making use of the following fact:

Theorem. If we randomly choose a feedback polynomial whose period divides $2^n-1$, then the probability that the period of the LFSR divides $(2^n-1)/q$ is $\le 1/q$.

Proof: Suppose $f(x)$ is a feedback polynomial for which the corresponding LFSR has period dividing $2^n-1$. Then $f(x)$ is irreducible and $GF(2)[x]/(f(x))$ is a finite field of size $2^n$. But there is only one, unique finite field of size $2^n$, so there is a field isomorphism between $GF(2)[x]/(f(x))$ and $GF(2^n)$, say $\varphi : GF(2)[x]/(f(x)) \to GF(2^n)$.

Now let's look at the next-state function for the LFSR with feedback polynomial $f(x)$. It corresponds to multiplying by $x$ in $GF(2)[x]/(f(x))$. Let $g=\varphi(x)$; applying $\varphi$, we see that the next-state function can also be thought of as multiplying by $g$ in the group $G=GF(2^n)^*$. Note that the order of $g$ is equal to the period of the LFSR with feedback polynomial $f(x)$, since $x^k \equiv 1 \pmod{f(x)}$ iff $g^k=1$. And, of course, $G$ has order $2^n-1$.

In this way, we obtain a bijection between feedback polynomials $f(x)$ and elements $g \in G$, where the period of the feedback polynomial is equal to the order of $g$. The probability that a randomly chosen element $g \in G$ has period dividing $(2^n-1)/q$ is $\le 1/q$, from which the theorem follows (by applying $\varphi^{-1}$).