¿Cuáles son los pasos a seguir para resolver un polinomio cuartico modulo a modulo primario?

Question

Esto: $$x^4 + 21x^3 + 5x^2 + 7x + 1 \equiv 0 \mod 23$$

Lleva a: $$x = 18 || x =19$$

Lo sé porque de este ejemplo de Wolfram-Alpha y porque un compañero lo publicó en una pregunta relacionada y suprimida desde entonces .

Lo que no entiendo son los pasos que hay que dar para llegar a x = 18 || x = 19 de esta ecuación.

Mi pregunta comienza con el ejemplo del mod 23 de términos reducidos en el pregunta relacionada . Ahora estoy tratando de entender cómo reducir esta ecuación a x = 18 || x = 19 .

Me he encontrado con unos cuantos postes y teoremas que sugieren una solución, pero me falta la habilidad matemática para conectar todo esto. Soy un desarrollador de software, no un matemático. Así que si alguien puede guiarme a través de algunos pasos sobre cómo pasar de la ecuación a 18 || 19 ¡Estaría muy bien!

Este es un ejemplo de juguete que representa una nueva operación de criptografía de curva elíptica donde el módulo real es $2^{256}$ grande. Así que, intentar todos los valores posibles x no es práctico. WolframAlpha es capaz de producir soluciones a mis ecuaciones de módulo grande en una fracción de segundo, así que sé que no están intentando todos los valores posibles x.

Fermat’s Little Theorem parece la más prometedora hasta ahora, pero no entiendo cómo aplicarla a esta ecuación. Este puesto describe una solución, pero desgraciadamente su ejemplo es muy básico y no muy relacionado con mi ecuación.

Cualquier cosa sería útil aquí. Los pasos serían geniales. Gracias.

Answer 1

Si se me pidiera que "resolviera" un módulo de polinomio cuartico (mono, entero) un módulo primario ( $23$ en el problema de los juguetes descrito aquí), primero determinaría si el polinomio puede ser factorizado sobre los racionales (equiv. sobre los enteros por el lema de Gauss).

Aquí el polinomio resulta ser irreducible sobre los números enteros:

$$ f(x) := x^4 + 21x^3 + 5x^2 + 7x + 1 $$

Si hubiera un factor de grado uno en $ \mathbb Z[x]$ entonces por el Teorema de las Raíces Racionales habría una raíz $ \pm 1$ . Es fácil comprobar que no es así. La única otra factorización posible sobre $ \mathbb Z[x]$ sería el producto de dos cuadráticos:

$$ (x^2 + ax + 1)(x^2 + bx + 1) $$

o:

$$ (x^2 + ax - 1)(x^2 + bx - 1) $$

Estas posibilidades pueden descartarse comparando los coeficientes de $x^3$ y $x$ que resultaría, ya que esto da valores inconsistentes de $a+b$ .

Es una frustración menor, pero si $f(x)$ no se ha tenido en cuenta en los números enteros, sino que también se ha tenido en cuenta en los números enteros mod $p=23$ . Lo contrario no es válido. Sucede a menudo que los polinomios factor modulo un entero pero son irreducibles sobre los racionales (enteros).

Ahora llegamos a una conexión con el Pequeño Teorema de Fermat:

$$ x^p \equiv x \bmod p $$

para cualquier módulo principal $p$ . Una afirmación más fuerte es que no sólo todos los residuos están modificados $p$ raíces de $x^p - x$ esto $p$ El polinomio de tercer grado es el producto de todos los polinomios irreductibles de primer grado mod $p$ . Ver estas notas de clase (Prop. 1) para una propuesta más general.

Por lo tanto, podemos proceder, con suerte, a calcular el GCD polinomio de $f(x)$ y $x^p - x$ que dará el producto de todos los factores de primer grado de $f(x)$ . Ahora si $f(x)$ se divide sobre los números enteros mod $p$ nos gustaría tener $f(x)$ lo que significaría cuatro raíces distintas sin decir cuáles son. Pero en el presente caso (con dos raíces distintas), en lugar de eso conseguiremos $f(x)$ factorizado como un producto de dos cuadráticos mod. $p$ .

Ahora tengo que interrumpir la escritura de los detalles, pero volveré y mostraré cómo (con pequeñas $p=23$ ) este cálculo puede hacerse a mano.

Answer 2

Yo también creo, como Saulspatz, que para los módulos pequeños uno podría probar todos los valores posibles.

Otra idea que podría funcionar para algunas ecuaciones simples es la siguiente, aunque debería ser una técnica de último recurso (aquí pude hacerla funcionar sólo porque ya conocía las soluciones):

Desde $$21 = -2 + 23, \quad 5 = -64 + 3 \cdot 23, \quad 7 = -85 + 4 \cdot 23, \quad 1 = 300 - 13 \cdot 23$$ la ecuación es equivalente a: $$x^4 - 2 x^3 - 64x^2 - 85 x + 300 \equiv 0 \pmod {23}$$ Ahora, por el teorema de la raíz integral, comprobamos si algunos divisores de $300$ son raíces del polinomio sobre $ \mathbb Q$ . En efecto, $$(-4)^4 - 2(-4)^3 - 64 (-4)^2 - 85 (-4) + 300 = 0$$ $$(-5)^4 - 2(-5)^3 - 64 (-5)^2 - 85 (-5) + 300 = 0$$ Dividimos el polinomio por $(x + 4)$ y $(x + 5)$ obteniendo..: $$(x + 4)(x + 5)(x^2 - 11x + 15) \equiv 0 \pmod {23}$$ Finalmente, ya que $ \Delta = (-11)^2 - 4 \cdot 15 = 61 \equiv 15 \pmod {23}$ y $15$ no es un módulo de residuos cuadrático $23$ las únicas soluciones son $-4$ y $-5$ .

Answer 3

Si una de las raíces ( $x=19$ ) se conoce entonces la descomposición de la ecuación no es difícil.

La sustitución $$x=y-4, \tag1 $$ da la menor suma de los coeficientes, donde una de las raíces debe ser cero: $$y^4+5y^3-151y^2+719y-1035=0,$$ $$y^4+5y^3+10y^2+6y \equiv0\pmod {23}. \tag1 $$ Si no se conocen las raíces, la forma más fácil es comprobar los valores de los polinomios por módulo $23$ .

El teorema de la Vieta puede aumentar el busto de la siguiente manera.

Si $x=0,$ entonces el valor del polinomio es 1, con los divisores $ \pm1. $

Si $x=1,$ entonces el valor del polinomio es 12, con los nuevos divisores $ \pm2 , \pm3 , \pm4 , \pm6 , \pm12 $ etc.

Esto permite comprobar sólo los valores posibles.

La ecuación $(1)$ puede descomponerse en forma de $$y(y+1)(y^2+4y+6) \equiv0\pmod {23}, \tag2 $$ con las raíces $y \equiv -1,0 \pmod {23},$ $$ \mathbf { \color {brown}{x \equiv18 ,19 \pmod {23}.}}$$ La ecuación se vuelve cúbica. Se puede usar la forma anterior.

Al mismo tiempo, la ecuación cuadrática $$y^2+4y+6 \equiv 0 \pmod {23}$$ es bien conocido. No tiene las raíces enteras.

En parte, esto se puede probar, usando las tablas de residuos cuadráticos. Pero si el módulo es pequeño, el busto parece más fácil.

Answer 4

Los métodos generales para resolviendo los cuartiles a través de los radicales modulo de trabajo $23$ IIRC trabajan en todas las características excepto en la 2 y la 3, así que podrías aplicarlas si sabes cómo tomar raíces cuadradas y cúbicas. Esto a menudo requerirá algún cálculo intermedio en los campos de extensión

23 es un pequeño, así que simplemente probar cada valor posible y comprobar si es una raíz es factible, especialmente a través de un programa. Por supuesto, esto es menos factible para los grandes primos.

Sin embargo, el método general para este tipo de problemas consiste básicamente en aplicar una algoritmo de factorización polinómica para campos finitos para descubrir los factores lineales de tu polinomio.

El hecho de que sólo busques las raíces en lugar de la factorización completa no simplifica realmente estos métodos generales, aunque con cuidado te permitiría hacer menos trabajo. Por ejemplo, si se utiliza un método que comienza con la "factorización de grado distinto", sólo se necesita el factor que da el producto de los factores lineales.

Answer 5

También existe el siguiente camino.

Deje que $k$ ser un número entero.

Así, $$x^4 + 21x^3 + 5x^2 + 7x + 1 \equiv x^4-2x^3+5x^2+7x+1=$$ $$=(x^2-x+k)^2-((2k-4)x^2-(2k+7)x+k^2-1)).$$ Ahora, elegiremos un valor de $k$ para el cual $$(2k+7)^2-8(k-2)(k^2-1) \equiv0. $$

Vemos que $k=6$ es válido.

Id est, $$x^4 + 21x^3 + 5x^2 + 7x + 1 \equiv (x^2-x+6)^2-(8x^2-19x+35) \equiv $$ $$ \equiv (x^2-x+6)^2-(100x^2-180x+81)=(x^2-x+6)^2-(10x-9)^2=$$ $$=(x^2-11x+15)(x^2+9x-3)$$ y el resto es suave.