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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum