Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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 at 22:56
6  
Every element has a square root in a finite field of even order. –  Felipe Voloch Apr 11 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 at 23:03
    
@Felipe: You are right, that was my mistake. This answers my question. Thank you very much. –  Dimitri Apr 11 at 23:19
    
IIRC, you can repeat the derivation of the cubic formula. –  Hurkyl Apr 12 at 4:56

1 Answer 1

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.

share|improve this answer
    
Nice idea; it is amazing that linear algebra can be exploited to solve a cubic equation. Are there any similar tricks in other characteristics , especially 0? –  P Vanchinathan Apr 12 at 2:48
    
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 at 4:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.