6
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented Apr 11, 2014 at 22:56
  • 8
    $\begingroup$ Every element has a square root in a finite field of even order. $\endgroup$
    – Felipe Voloch
    Commented Apr 11, 2014 at 23:01
  • $\begingroup$ 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. $\endgroup$
    – Dimitri
    Commented Apr 11, 2014 at 23:03
  • $\begingroup$ @Felipe: You are right, that was my mistake. This answers my question. Thank you very much. $\endgroup$
    – Dimitri
    Commented Apr 11, 2014 at 23:19
  • $\begingroup$ IIRC, you can repeat the derivation of the cubic formula. $\endgroup$
    – user13113
    Commented Apr 12, 2014 at 4:56

1 Answer 1

Reset to default
28
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – P Vanchinathan
    Commented Apr 12, 2014 at 2:48
  • 1
    $\begingroup$ If $q = 0$, then you have $2^d$ solutions. Of course, you could divide by $z$ rather than multiply by $z$ in that case. $\endgroup$
    – user13113
    Commented Apr 12, 2014 at 4:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .