Deje $F_q$ ser un campo finito. ¿Cuál es el mejor algoritmo para probar si un polinomio $f$ es un cuadrado? Sólo estoy interesado en el régimen q pequeño respecto al grado de $f$.
Respuesta
¿Demasiados anuncios?
Eric Towers
Puntos
8212
Calcular $g = f/\gcd(f, f')$, (de forma recursiva) determinar si $h = f / g^2$ es un cuadrado.
Si $f$ es un cuadrado, entonces, de sus raíces ocurrir incluso con la multiplicidad, por lo que tiene un trivial $\gcd$ con su derivada. A continuación, $g$ tiene raíces que son los repetidos raíces de $f$ con sus multiplicidades reducido a $1$. A continuación, $h$ $f$ con todas las multiplicidades de sus repetidas raíces reducido por $2$. La iteración, se obtiene una secuencia de $h$s, $h_1, h_2, \dots h_k$, que termina cuando se $2k \geq \deg f$ (es decir, cuando se $\gcd(f,f') = 1$) debido a las multiplicidades de las raíces de la $f$ son finitos. Si $h_k$ es una constante, entonces $h_{k-1}$ es un cuadrado, y así sucesivamente, deshaciendo hasta el $f$ es un cuadrado. Si $h_k$ no es una constante, entonces $h_{k-1}$ no es un cuadrado, y así sucesivamente, deshaciendo hasta el $f$ no es un cuadrado.
Esta es una adaptación de la habitual primer paso de la factorización de polinomios, la reducción a la plaza de forma libre. Ver aquí para más información sobre este paso.
Añadido en editar:
Una forma de detectar que $h$ no es un cuadrado polinomio es que $h$ no es un polinomio. Que es $g^2 \nmid f$. (Nuestra forma de construir la $g$ asegura que esto no puede suceder aquí, pero es una cosa que puede suceder, más en general la configuración.)
Tenga en cuenta que este es "complicado" en el carácter $2$. Que me ponga entre comillas porque cada elemento es un cuadrado en el carácter $2$ (debido a la Frobenius mapa es surjective en campos finitos), de manera mucho más fácil algoritmo en el carácter $2$ (No se muy bien que es fácil, pero aún fácil.)return True.
Knuth (el Arte de la Programación informática, Vol. 2, p. 446) analiza el algoritmo de Berlekamp modulo de un primer $p$. El primer paso en el algoritmo de Berlekamp, "paso B1", calcula el $\gcd(f,f')$ $O(n^2)$ del tiempo. Para un gran $q$, sustituir esto con $O(n^2 (\log q)^2)$ a cuenta por el tiempo de computación, invierte en $\mathbb{F}_q$ (por cualquiera de varios métodos). Aquí, $n = \deg f$. El algoritmo anterior tiene en la mayoría de los $\deg f/2$ $\gcd$s, por lo que parece ser $O(n^3)$ para su caso de las pequeñas $q$.
Wikipedia sugiere que el algoritmo de Berlekamp y el Cantor-Zassenhaus algoritmo son el ir-a los algoritmos de factorización sobre campos finitos. Ambos se basan en $\gcd$s, así que no veo que hay evidente alternativas para el algoritmo anterior.
Allí están algunos de los furtivos de los algoritmos de factorización modulo de los números primos, $p$, habiendo $p-1$ liso (es decir, la factorización en números pequeños). Ver Factorizar polinomios modulo especial de los números primos. Yo no estoy familiarizado con estos métodos.
