Roots of the Cubic Equation in F2^M

Date: 07/20/2000 at 08:14:35
From: Kamran Ahmed
Subject: Cubic equation roots in F2^M

Is there a general solution for the roots of the cubic equation

     a*x^3 + b*x^2 + c*x + d = 0

where x is an element of the finite field F2^M? If there is, I'd be 
grateful to know what it is. I have looked extensively on the Web, in 
vain. 

Many thanks and regards.

Date: 07/20/2000 at 13:13:43
From: Doctor Rob
Subject: Re: cubic equation roots in F2^M

Thanks for writing to Ask Dr. Math, Kamran.

Start by reducing the problem to a simpler one. If a = 0, the equation 
is not cubic, so we can assume a is nonzero. Multiply through by its 
inverse in F2^M, and reduce to an equation with leading term x^3. Thus 
we can assume that a = 1. If b is nonzero, substitute x = y + b. This 
will reduce the equation to one with no x^2 term, so we can assume 
that b = 0. Now the equation has the form

     x^3 + c*x + d = 0.

Let x = y + c/y. This leads to the equation

     y^6 + d*y^3 + c^3 = 0.

This is a quadratic equation in y^3. There are two possibilities. 
Either z^2 + d*z + c^3 is irreducible over F2^M, or it is not. If it 
is irreducible, then by adjoining a root of it to F2^M, we get an 
extension field F2^M(z) ~= F2^(2*M), and in that field, the polynomial 
is reducible, and factors into (z+e)*(z+f) with e and f in 
F2^(2*M) - F2^M. If it is reducible, it factors into (z+e)*(z+f) with 
e and f in F2^M. Next, we have to find y, and we know that either

     y^3 = e  or  y^3 = f.

Thus we have to take a cube root of an element in F2^(2*M) or in F2^M.

Now e is a perfect cube in F2^(2*M) if and only if

     e^((2^(2*M)-1)/3) = 1,

and likewise for f. If it is a perfect cube, then there are three cube 
roots in F2^(2*M). Each of them will give a value of x = y + c/y. This 
will not be in F2^M. If it is not a perfect cube, then there will be 
three cube roots lying in F2^(6*M) - F2^(2*M). Each of them will give 
a value of x = y + c/y, which will not be in F2^(2*M).

When e is in F2^M, there are two possibilities, depending on M. If M 
is odd, then there is a unique cube root of e in F2^M, given by 
e^((2^(M+1)-1)/3), and two cube roots in F2^(2*M). The former will 
give a value of y and therefore a value of x which both lie in F2^M. 
The latter two will give values of y and x which do not lie in F2^M.

On the other hand, if M is even, then either e is a perfect cube in 
F2^M, or not. e is a perfect cube in F2^M if and only if

     e^((2^M-1)/3) = 1.

If e is not a perfect cube in F2^M, then the values of y lie in 
F2^(3*M), and so do the values of x. In case e is a perfect cube in 
F2^M, there are three cube roots of e in F2^M, and so three values of 
y and hence x in F2^M.

To find the three cube roots of e in F2^M when M is even and e is a 
perfect cube is not so easy. There are no formulas to do this, and the 
best algorithm I know is probabilistic, but effective.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/