# How can I solve a cubic equation in a finite field with characteristic 2?

I need to solve the usual cubic equation $x^3 + ax^2 + bx + c = 0$ over a finite field $GF(2^n)$. This is to avoid doing a brute-force Chien search in a BCH decoder.

I read in a paper about an easy way to reduce the equation to $z^3 + z + k = 0$ where $k = (a b + c) / (a^2 + b)^{3/2}.$ Then a lookup table can be used for all the values of $k$. However as far as I can tell this approach will not work when $(a^2 + b)$ happens to not have a square root in the field. An example for $GF(2^5)$ would be $x^3 + 08*x + 1a = 0.$

Can someone help?

Regards,
-Dimitri

-
I don't know what 08 is (a coefficient in your example cubic). But it's possible that a cubic has no solution in a given finite field, right? Anyway, MO is for math research --- I don't see where there's a research angle to your question. – Gerry Myerson Apr 11 '14 at 22:56
Every element has a square root in a finite field of even order. – Felipe Voloch Apr 11 '14 at 23:01
Yes certainly it is possible. The point of the example was to demonstrate that there are cubic equations that have solutions for which (a^2 + b) does not have a sq root. The 08 is the hex representation of a GF(2^5) element - in binary form it would be '01000', equal to a^3, a being the prime element. This equation does have (at least) one root: For x=10 ('1000' = a^4) it becomes zero, yet (a^2+b) which is equal to b (=08=a^3) in this case does not have a square root because it equals an odd power of a. – Dimitri Apr 11 '14 at 23:03
@Felipe: You are right, that was my mistake. This answers my question. Thank you very much. – Dimitri Apr 11 '14 at 23:19
IIRC, you can repeat the derivation of the cubic formula. – Hurkyl Apr 12 '14 at 4:56

An alternative approach that works even when $n$ is too large to store a table of size $2^n$: translate $x$ by $a$ to get $z^3+pz+q = 0$ where $z=x+a$; then multiply by $z$ to get $z^4 + pz^2 + qz = 0$.
The point of this last step is that the map $z \mapsto z^4 + pz^2 + qz$ is $({\bf Z} / 2{\bf Z})$-linear because the exponents $1,2,4$ are all powers of $2$. Therefore the problem is reduced to finding the kernel of an $n \times n$ matrix over $({\bf Z} / 2{\bf Z})$. The equation $z^3+pz+q=0$ (without the factor of $z$) then has $2^d - 1$ solutions where $d \in \{0,1,2\}$ is the dimension of the kernel.
If $q = 0$, then you have $2^d$ solutions. Of course, you could divide by $z$ rather than multiply by $z$ in that case. – Hurkyl Apr 12 '14 at 4:53