Resolución de ecuaciones polinómicas en campos finitos

Question

He mirado (un poco) cuestiones como encontrar el número de raíces de $x^n =1$ sobre un campo finito.

Ahora me gustaría entender cómo resolver ecuaciones polinómicas sobre campos finitos. Por lo que entiendo la solución de la ecuación cuadrática tiene la misma fórmula de solución. Eso significa que todo se reduce a encontrar raíces cuadradas.

Sé que hay fórmulas para resolver ecuaciones de mayor grado, pero me pregunto si algunas de estas cosas son diferentes de alguna manera sobre un campo finito.

Pido una referencia que trate específicamente de la resolución de ecuaciones polinómicas sobre campos finitos. Estaría bien que la referencia fuera accesible para un estudiante de grado avanzado.

Answer 1

Resolver polinomios en una variable sobre campos finitos es sustancialmente más fácil que resolver polinomios en general. Para saber si $f(x) = 0$ tiene cualquier raíz sobre $\mathbb{F}_q$ sólo hay que calcular $\gcd(f(x), x^q - x)$ utilizando el algoritmo euclidiano, ya que las raíces de $x^q - x$ son precisamente los elementos de $\mathbb{F}_q$ . Una elaboración de esta idea conduce a un algoritmo eficiente no sólo para resolver sino incluso para factorizar polinomios sobre campos finitos; véase El algoritmo de Berlekamp para más detalles.