How can one solve an equation over over a specific finite field?

Question

How can one solve an equation of the following form where the coefficients are in $GF(2^{128})$?

$Az^3 + Bz^2 + Cz + D = 0$

The operations are defined over the same field.

Answer 1

A rough sketch of a method that I think I could implement (given enough time and motivation). It is not deterministic, and it is probably nowhere near state of the art.

Let $K=GF(2^{128})$. Consider the trace mapping $tr:K\to GF(2)$ defined as the sum of iterates of the Frobenius automorphism $$ tr(x)=x+x^2+x^4+x^8+x^{16}+\cdots+x^{2^{127}}=\sum_{i=0}^{127}x^{2^i}. $$ For all $z\in K$ we have either $tr(z)=0$ or $tr(z)=1$ with both values appearing equally frequently. Because the trace is the sum of automorphisms it is a homomorphism of additive groups, $tr(x+y)=tr(x)+tr(y)$. Let $H\subseteq K$ be the kernel of the trace. It is subspace over the prime field $GF(2)$, of dimension 127.

The task at hand is to find the zeros ($\in K$) of the given cubic $$ p(x)=Ax^3+Bx^2+Cx+D\in K[x]. $$ The method I describe actually works for all low degree polynomials provided that all the roots of $p(x)$ are simple. That can be checked by calculating the gcd of $p(x)$ and $p'(x)$. There is general method for writing $p(x)$ as a product of square free factors, but I'm afraid I don't remember how it goes.

It is well known that all the elements of $K$ are zeros of the polynomial $q(x)=x^{2^{128}}-x$. It is easy to see that the zeros of $p(x)$ that are also elements of $K$ are exactly the zeros of $$p_0(x)=\gcd(q(x),p(x)).$$ The calculation of this gcd may look prohibitive, but it actually has a reasoanbly low complexity. This is because if $r_k(x)$ is the remainder of $x^{2^k}$ modulo $p(x)$, then $$ r_{k+1}(x)\equiv r_k(x)^2\pmod {p(x)}. $$ In other words calculating the remainder of $q(x)$ modulo $p(x)$ only needs 128 squarings of low degree polynomials modulo the given cubic. We actually never need to carry out long division for polynomials of degrees higher than $2(\deg p(x) -1)$. After the initial computation Euclid's algorithm will only ever need to do long division of low degree polynomials, which has reasonable complexity.

Ok, so assume that we know $p_0(x)$. For all we know it could still be a cubic (or higher) that we cannot solve using a formula. The next step is non-deterministic. We pick a random element $\alpha\in K, \alpha\neq0$. We want to $p_0(x)$ into two factors $$ p_0(x)=p_1(x)r_1(x) $$ such that $p_1(x)$ has as its zeros those zeros of $p_0(x)$ that are in the subspace $\alpha^{-1}H$. This means that $$ p_1(x)=\gcd(p_0(x),tr(\alpha x)). $$ Here the polynomial $tr(\alpha x)$ again has a disgustingly high degree, but its terms are all squares of the preceding one, so the sum of their remainders modulo $p_0(x)$ can be calculated with a reasonably complexity.

Given $p_1(x)$ we can find $r_1(x)$ by long division.

If either $p_1(x)$ or $r_1(x)$ is of degree one, we can find its zero (using the half-trace trick we could also find the zeros of a quadratic). Next we continue with the remaining non-linear factors by selecting another random $\alpha$ and repeating the above calculations.

Does this work? There may be pitfalls, but do observe that if $\alpha\neq\beta$, then the spaces $\alpha^{-1}H$ and $\beta^{-1}H$ intersect in a codimension one subspace. Therefore the bits of information about the identity of a zero of $p(x)$ obtained by using these two variants of the trace are independent from each other. I haven't checked out everything, but I think this means that random choices of $\alpha$:s should work sooner rather than later.

[I hope to add a toy example with $GF(16)$ here, but it will have to wait for tomorrow or may be a bit more.]