Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Modern Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search