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

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)$.

• Why would you need a LFSR of length $n=2991$? (1) Why would you need such a long LFSR? (2) Even if you needed a LFSR that has at least 2991 bits of state for some reason I haven't anticipated, why can't you just use a slightly larger LFSR, say $n=2992$? – D.W. Jan 10 '14 at 18:23
• @D.W.: I do not need an LFSR, much less one any near (or exactly) 2991 bits (that part came as an excuse to point to a fascinating effort, that occasionaly has some applications). However I'd like moderate size LFSRs (like 320 bits) to illustrate an article on the ASG, arguably the simplest (conjectured) CSPRNG with a demonstrably long period and constant work per bit ouput. In turn I'd like a simple program testing that an LFSR is maximal-length, and for this I'd like to get rid of the requirement to have the factors of $2^n−1$. – fgrieu Jan 10 '14 at 20:40
• Well, that's a different problem statement. You might do better by asking about the actual problem you want to solve. I think the simplest solution to that problem will involve factoring $2^n-1$. I think you are over-estimating the complexity of that approach. You should be able to factor $2^{320}-1$ using standard tools, without breaking a sweat. (cont.) – D.W. Jan 10 '14 at 22:39
• For instance, the Unix factor commands factors $2^{320}-1$ in 1.5 seconds, yielding the factorization $2^{320}-1 = 3 \times 5 \times 5 \times 11 \times 17 \times 31 \times 41 \times 257 \times 641 \times 61681 \times 65537 \times 414721 \times 3602561 \times 6700417 \times 4278255361 \times 44479210368001 \times 94455684953484563055991838558081$. – D.W. Jan 10 '14 at 22:39

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}$).

• I think that we should choose the feedback polynomial with terms $x^n$ and the constant term set, else I have no proof that even the classical algorithm is correct. We could also choose it with an odd number of terms, since that's a necessary condition for maximal length. Independently: I'd like that others could run the algorithm to check that a LFSR that I propose is maximal-length; if randomizing the non-zero starting state (and perhaps making a few iterations) was demonstrably enough for low odds of letting a non-maximal LFSR creep, that would be perfect; but I'm unsure that holds. – fgrieu Jan 13 '14 at 8:49
• @fgrieu, OK, those are good points. I've added those to the algorithm. Setting the constant term and requiring an odd number of taps is just an optimization. (If you choose a polynomial that doesn't have the low bit set, then it'll fail the check that its period divides $2^n-1$ and will be rejected in step 3 of my algorithm.) – D.W. Jan 13 '14 at 8:58
• @fgrieu, yup, it doesn't allow you to verify that a LFSR given to you by someone else is maximal-length. However, as I suspect you already know, if you want to generate a LFSR that others can verify is probably maximal-length, you could seed a deterministic PRNG (DRBG) with a "nothing-up-my-sleeve number", and then use the output of that PRNG as the random numbers for my algorithm. That'll allow anyone else to verify that you've generated the LFSR polynomial in a way that you can't easily bias. The security level will depend on the value of $n$. – D.W. Jan 13 '14 at 9:39
• I get your proof, and it solves my (now gone) interrogation of what $g$ in the generator framework maps to in the LFSR framework. The algorithm allows me to choose a random LFSR that is maximal-length with high probability, and convince someone that I did so. Many thanks! I can't refrain to note that it does not work well for generating a LFSR corresponding to a sparse polynomial, e.g. a trinomial, which has some computational advantage. – fgrieu Jan 13 '14 at 19:56