How do you discover an irreducible polynomial over a finite field that has a chosen degree?

Question

I'm would like to find a few polynomials of degree 127 irreducible over $\mathbb{F}_2$ for use in constructing $GF(2^{127})$. This is because I'm thinking of trying to make my own version of AES-GCM that doesn't have the small-subgroup problem (because it currently uses $GF(2^{128})$). And since $2^{127}-1$ is a Mersenne Prime, every element except 1 and 0 will be a generator for the whole field under multiplication.

Are there any good techniques for discovering such polynomials quickly? I've been picking polynomials randomly and testing with Fermat's Little Theorem on a few randomly chosen field elements (aka does $a^{2^{127}-1} \mod p = 1$ where $a$ is a polynomial with degree < 127 over $\mathbb{F}_2[x]), a \notin \{0,1\}$ and $p$ is my candidate polynomial?). Is there a better way? Are there any pitfalls for my way?

Please forgive me if I've stated things imprecisely or used the wrong terminology. I'm primarily a software engineer who's learned some abstract algebra because I like knowing the math stuff is based on rather than blindly implementing it.

Answer 1

I'm not sure whether this is what the OP had in mind, but here is one way of testing whether a given polynomial of degree $127$ from $GF(2)[x]$ is irreducible. This relies on $127$ being a prime number, but some modifications could be made to work for other for non-primes also, I think. This is not for paper & pencil work, just a simple test you can do, if you have implemented arithmetic of polynomials with coefficients in $GF(2)$.

Input: A polynomial $p(x)\in GF(2)[x]$ of degree $127$.

Goal: Determine whether $p(x)$ is irreducible over $GF(2)$.

Assumptions:

• I assume that $p(x)$ is square-free. In other words, there are no non-constant polynomials $q(x)\in GF(2)[x]$ such that $q(x)^2\mid p(x)$. This is easy to test. All you need to do is to calculate $\gcd(p(x),p'(x))$ with the Euclidean algorithm. Here $p'(x)$ is the (formal) derivative of $p(x)$. If $q(x)^2\mid p(x)$, then also $q(x)\mid p'(x)$, and hence $q(x)$ is a common factor of $p(x)$ and $p'(x)$. So if the gcd is equal to one, then $p(x)$ is square-free. Otherwise we can immediately conclude that $p(x)$ is not irreducible.
• For simplicity we can also assume that $p(0)=1$. For otherwise $p(0)=0$, $x$ is a factor, and $p(x)$ is trivially not irreducible.

Claim (or the algorithm): The input polynomial $p(x)$ is irreducible in $GF(2)[x]$ if and only if $$ x^{2^{127}}\equiv x\pmod {p(x)}. $$ Here the remainder of $x^{2^{127}}$ modulo $p(x)$ can be efficiently calculated with repeated squaring. In other words we recursively define the sequence of polynomials $(r_n)$ of degrees $<127$ as follows:

• $r_0(x)=x$,

• if we have calculated $r_k(x)$, we then calculate $r_{k+1}(x)$ as the remainder of $r_k(x)^2$ modulo $p(x)$,

• then $r_{127}(x)$ is the desired remainder.

Proof. This test shows that $p(x)$ is a factor of $S(x):=x^{2^{127}}-x$. Because $127$ is a prime, this implies that $p(x)$ is irreducible. All factors of $S(x)$ of degree $127$ are irreducible because $S(x)$ is known to be the product of all the irreducible polynomials of degrees that are factors of $127$. In the present case, the degrees of irreducible factors of $S(x)$ are thus $1$ or $127$, and all such irreducible polynomials appear.

---

Remarks. This is mostly about generalizing the above test to non-prime degrees.

1. In the case of degree $127$ the square-free test was superfluous. It becomes necessary, if instead of degree $127$ we study the irreducibility of polynomials of non-prime degrees. See the next item.
2. If, in the general case, $p(x)$ is a square-free polynomial of degree $m$, then it is a product of distinct irreducible factors, say $$p(x)=p_1(x)p_2(x)\cdots p_k(x).$$ In this case the Chinese Remainder Theorem tells us that the quotient ring $$GF(2)[x]/\langle p(x)\rangle\simeq \bigoplus_{i=1}^kGF(2)[x]/\langle p_i(x)\rangle.$$ Consequently $x^{2^\ell}\equiv x\pmod {p(x)}$ if and only if $x^{2^\ell}\equiv x\pmod{p_i(x)}$ for all $i=1,2,\ldots,k$ if and only if $\ell$ is divisible by the degrees $\deg p_i(x)$ of all the irreducible factors.
3. From the previous remark we see that that if $m$ is the least common multiple of the degrees $\deg p_i(x), i=1,2,\ldots,k$, then the polynomial $p(x)$ passes the simple test of the main algorithm. We can soup up the algorithm by testing whether the polynomial $r_d(x)-x$ has a common factor with $p(x)$ for those values of $d$ such that $d\mid m$. This will then catch $p(x)$ is reducible. Namely, if $p_i(x)$ is a factor of degree $d$, then $p_i(x)$ is a common factor of $p(x)$ and $x^{2^d}-x$, and will thus be a factor of $r_d(x)-x$.
4. The OP discussed testing the remainder of $a^{2^{127}-1}$ modulo $p(x)$ for some generic element $a\in GF(2^{127})\setminus GF(2)$. I'm not sure what they wanted to do here, because without the irreducible polynomial $p(x)$ we may not have implemented the field $GF(2^{127})$ yet. The main algorithm uses the coset of $x$ modulo $p(x)$ as a generic element of a "candidate field" $GF(2)[x]/\langle p(x)\rangle$ much the same way, so in that sense the method works. Indeed, because $2^{127}-1$ is also a prime, the order of $x$ must be precisely $2^{127}-1$ in the positive cases.

Answer 2

In general this is difficult (in the sense that I don't know a general method for finding one), but with degree $127$ the following special trick springs to mind.

Consider the polynomial $L(x)=x^{128}+x^2+x\in GF(2)[x]$. It is the linearized associate of the polynomial $m(x)=x^7+x+1$ (replace exponent $\ell$ with $2^\ell$ throughout to get the linearized associate). It is easy to verify that $m(x)$ is irreducible:

• It has no zeros in $GF(2)$ and hence no linear factors in $GF(2)[x]$.
• It is not divisible by the one and only irreducible quadratic $x^2+x+1$, because that is a factor of $x^3+1$ and hence also of $x^6+1$ and $x^7+x$.
• It is not divisible by either of the irreducible cubics, because those are factors of $x^7+1$.

The zeros of $m(x)$ are thus elements of $GF(2^7)$, and because $2^7-1=127$ is a prime those zeros have order $127$. Therefore $m(x)\mid x^{127}-1$ in $GF(2)[x]$. Again, by the theory of linearized and conventional associates this implies that $$ L(x)\mid x^{2^{127}}-x. $$ Namely, if a polynomial divides another, then its linearized associate divides the linearized associate of the other even symbolically (= as an innermost composition factor), and hence also in the polynomial ring.

But, $GF(2^{127})$ is well known to consist of the zeros of $p(x)=x^{2^{127}}-x$. Again, as $127$ is a prime, this implies that apart from the trivial factors $x$ and $x-1$ all the irreducible factors of $p(x)$ have degree $127$.

Drums, please. We just saw that $$f(x)=L(x)/x=x^{127}+x+1$$ is a degree $127$ factor of $p(x)$. Hence it must be irreducible.

---

Repeating the dose, we arrive at the curious conclusion that because $M=2^{127}-1$ is a prime number, it follows that $$ F(x)=x^M+x+1 $$ is also irreducible in $GF(2)[x]$. By the properties of linearized associates $x^{2^{127}}+x^2+x$ is a factor of $x^{2^M}+x$. As all the non-linear irreducible factors of that polynomial have degree $M$ (because $M$ is prime) we can conclude that $F(x)$ is irreducible!

I wonder whether this "Mersenne tower" continues. It is beyond the existing technology, see a relevant Wikipedia page for more information.