Skip to main content
MathOverflow

Return to Question

TeX bug - sorry about not catching it right away.
Source Link
edit approved May 16, 2014 at 19:25
Jyrki Lahtonen
edit approved May 16, 2014 at 19:25
Jyrki Lahtonen
  • 1.4k
  • 10
  • 20

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).$$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

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

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

Some TeXifying
Source Link
edit approved May 16, 2014 at 19:19
Jyrki Lahtonen
edit approved May 16, 2014 at 19:19
Jyrki Lahtonen
  • 1.4k
  • 10
  • 20

I need to solve the usual cubic equation x^3 + ax^2 + bx + c = 0$x^3 + ax^2 + bx + c = 0$ over a finite field GF(2^n)$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) ^$z^3 + z + k = 0$ where (3/2).$k = (a b + c) / (a^2 + b) ^ (3/2).$ Then a lookup table can be used for all the values of k$k$. However as far as I can tell this approach will not work when (a^2 + b)$(a^2 + b)$ happens to not have a square root in the field. An example for GF(2^5)$GF(2^5)$ would be x^3 + 08*x + 1a = 0.$x^3 + 08*x + 1a = 0.$

Can someone help?

Regards,
-Dimitri

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

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

Source Link
Dimitri
Dimitri
  • 87
  • 5

How can I solve a cubic equation in a finite field with characteristic 2?

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