Ytukyg

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.

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)^2mid 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)^2mid 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 xpmod {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)ranglesimeq bigoplus_{i=1}^kGF(2)[x]/langle p_i(x)rangle.$$ Consequently $x^{2^ell}equiv xpmod {p(x)}$ if and only if $x^{2^ell}equiv xpmod{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 $dmid 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 $ain 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.

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+xin 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.