Divida $n$ en factores no triviales a través de una raíz cuadrada no trivial de $1\!\pmod{\!n}$

Question

Viniendo de una comprensión de la prueba de primalidad de Fermat, estoy buscando una explicación clara de la prueba de primalidad de Miller-Rabin.

Específicamente: Entiendo que por alguna razón, tener raíces cuadradas no triviales de $1 \bmod p$ significa que $p$ es definitivamente compuesto; y entiendo que puedes encontrar estas raíces cuadradas no triviales al cuadrar $x$, pero realmente no entiendo cuáles son esas razones. Ejemplos específicos de raíces no triviales de un número compuesto serían útiles.

¡Saludos!

Answer 1

Supongamos que $p$ era primo, y $y$ era una raíz cuadrada no trivial de $1 \mod p$.

Entonces debemos tener que $y^2 = 1 \mod p$ y así $(y-1)(y+1) = 0 \mod p$. Esto implica que o bien $y = 1 \mod p$ o $y = -1 \mod p$, lo que implica que $y$ es una raíz cuadrada trivial.

Por lo tanto, si hay una raíz cuadrada no trivial de $1 \mod p$, entonces $p$ tiene que ser compuesto.

Para un ejemplo de una raíz cuadrada no trivial de un compuesto, consideremos $p = 15$. Tenemos que $4^2 = 16 = 1 \mod 15$. Así que $15$ es compuesto.

Observa que el testigo en la prueba de primalidad no es necesariamente una raíz cuadrada no trivial de $1 \mod p$.

El hecho sobre las raíces cuadradas no triviales se puede usar para demostrar que si $p$ es primo, entonces para cualquier $a$ relativamente primo a $p$, alguna potencia de $a$ de un conjunto dado de potencias (basadas en los factores pares de $p-1$) debe ser $-1$ o una potencia impar específica de $a$ (de nuevo basada en factores de $p-1$) debe ser $1$.

Si para algún $a$ ninguna de las anteriores potencias es $-1$ y la potencia impar específica no es $1$, entonces debe ser el hecho de que $p$ es compuesto.

También se puede demostrar que para $p$ compuesto, las probabilidades de encontrar dicho $a$ es al menos $3/4$. Este $a$ es el testigo en la prueba de primalidad y no es necesariamente una raíz cuadrada no trivial de $1 \mod p.

La elevación al cuadrado que se realiza es para obtener las potencias descritas anteriormente que se basan en los factores de $p-1$.

La página de wiki tiene realmente mucha buena información (incluidas las potencias exactas de $a$ que deben tomarse): Prueba de primalidad de Miller Rabin

Answer 2

La siguiente respuesta general pero poco conocida a tu pregunta sobre raíces no triviales $\rm (mod\ m)\:$

Teorema $ $ Podemos dividir rápidamente $\rm m>1\,$ en dos factores no triviales dados un polinomio distinto de cero con más raíces mod $\rm\, m\,$ que su grado.

Prueba $ $ Por hipótesis $\rm\, \color{#0a0}{0\not\equiv} f(x)\,$ tiene grado $\rm\,n\,$ y al menos $\rm\,n\!+\!1 \,$ raíces distintas $\rm\,r,\,r_1,\,\ldots,\,r_n.\,$ Aplicando inductivamente el Teorema del Factor como aquí obtenemos que alguna diferencia $\rm\,r_i-r_j\,$ es un divisor de cero no trivial (así que hemos terminado), o bien $\rm\,f(x) \equiv c(x\!-\!r_1)\cdots(x\!-\!r_{n}),\ c\color{#0a0}{\not\equiv 0}.\,$ Dado que además $\rm\,f(r)\equiv 0\,$ inferimos que $\rm\,m\mid c(r\!-\!r_1)\cdots (r\!-\!r_n).\,$ Si $\rm\,m\,$ fuera coprimo con todos esos factores, sería coprimo con su producto por el Lema de Euclides. Ya que no lo es, deducimos que $\rm\,m\,$ no es coprimo con algún factor $\rm\,k.\,$ Dado que $\,\rm m\,$ no divide a ninguno de los factores (por las raíces son distintas $\rm\!\bmod m\,$ y $\,c\color{#0a0}{\not\equiv 0}),\,$ inferimos $\,\rm\gcd(m,k)\neq m,\,$ así el mcd es un factor no trivial de $\,\rm m,\,$ siendo $\rm\neq 1,m.\ $

Ejemplo $\rm\;(deg\ f = 1)\;\,$ Supongamos, mod $\rm\,m,\,$ que $\rm\; 0 \,\not\equiv\, f \,=\, a\,x\;$ tiene una raíz "no trivial" $\rm\, b\not\equiv 0.\,$ Entonces $\rm\; m\mid ab,\,\ m\nmid a,b \;\Rightarrow\,$ $\,\rm gcd(m,b)\,$ es un factor de $\rm\, m\,$ que es no trivial $(\neq 1,\,m),\,$ es decir, $ $ cuando $\rm\, m\,$ falla en la Propiedad del Divisor Primo (Lema de Euclides) es constructivamente compuesto.

Ejemplo $\rm\;(deg\ f = 2)\;\,$ Supongamos, módulo $\rm\,m\,$, $\rm\; x^2 \equiv 1\,$ tiene una raíz cuadrada "no trivial" $\rm\, b\not\equiv \pm1.\,$ Entonces $\;\rm gcd(m,b\pm 1)\;$ produce un factor no trivial de $\rm\, m\,$ cuando $\rm\, m\,$ es impar. Esta idea es central en muchos algoritmos de factorización de enteros. Detalladamente, por factorización única en primos tenemos $\rm\, m\mid (b\!-\!1)(b\!+\!1)\,\Rightarrow\, m = jk,\,\ j\mid b\!-\!1,\, k\mid b\!+\!1,\,$ entonces $\rm\,m\nmid b\pm 1\,\Rightarrow\,j,k\mid m\,$ no trivialmente.

La prueba anterior se extiende fácilmente para demostrar lo siguiente

Teorema $ $ Un anillo $\rm\, R$ es un dominio (integral), es decir, $\rm\,rs = 0\,\Rightarrow\, r=0\,$ o $\rm\,s =0,\,$ para todo $\rm\,r,s\in R$ $\iff$ todo polinomio no nulo $\,\rm f(x)\in R[x]\,$ tiene a lo sumo $\rm\, deg\ f(x)\,$ raíces en $\rm R$

Prueba $\ $ $(\Rightarrow)\;$ Emplear inducción en el grado del polinomio, como en la demostración del Teorema anterior. $(\Leftarrow)\ \ $ Si $\rm\; r \ne 0\;$ entonces el polinomio $\rm\, rx\,$ tiene solo la raíz $\rm\; x = 0,\,$ entonces $\rm\ rs = 0 \ \Rightarrow\ s = 0$.

Answer 3

Si $p$ es primo entonces $\mathbb{Z}_p$ (enteros módulo $p$) es un campo. Es un resultado básico en álgebra que en un campo, un polinomio de grado $n$ tiene a lo sumo $n$ raíces, y así el polinomio $x^2-1$ tiene exactamente dos raíces: $1$ y $-1$ (que existen en todo campo).

Si $n$ es compuesto, entonces $\mathbb{Z}_n$ nunca es un campo porque no todos los elementos tienen inverso; es bien sabido que $a\in \mathbb{Z}_n$ tiene un inverso si y solo si $a$ es relativamente primo a $n$. Veamos el caso $n$ es el producto de dos primos, $n=pq$. En este caso podemos hacer aritmética en $\mathbb{Z}_n$ haciendo aritmética en $\mathbb{Z}_p$ y $\mathbb{Z}_q$ y combinando los resultados usando el teorema chino del resto (que básicamente establece que $\mathbb{Z}_n\cong\mathbb{Z}_p\times\mathbb{Z}_q$. Dado que $\mathbb{Z}_p$ y $\mathbb{Z}_q$ son ambos campos, $1$ tiene dos raíces en cada uno de ellos. Para cada combinación de una raíz de $\mathbb{Z}_p$ y una raíz de $\mathbb{Z}_q$ obtendremos una raíz de 1 en $\mathbb{Z}_n$, lo que significa que obtendremos 4 raíces de 1.

El desafío principal de la prueba de Miller-Rabin es mostrar que hay una "gran" probabilidad de tropezar con una raíz no trivial al elevar al cuadrado elementos aleatorios de $\mathbb{Z}_n$, y la demostración, aunque no es difícil, tampoco es inmediata.

Answer 4

Una prueba basada en el Teorema de Fermat ($a^{n-1} \equiv 1 \pmod n$ si $n$ es primo)

-Para un número entero impar candidato $n$ (3), considera $(n-1)$ tal que $n-1=2^kq$ con $k>0$, $q$ impar

Es decir, dividimos $(n-1)$ por 2 hasta que el resultado sea un número impar, totalizando $k$ divisiones.

-A continuación elegimos un entero $a$ ($1 < a < n - 1 $).

Luego involucra el cálculo de los residuos módulo $n$ de la siguiente secuencia de potencias

-$a^q, a^{2q}, ..., a^{2^{k-1}q}$, $a^{2^kq}$

-Si $n$ es primo, $a^{(2k-1)q} \equiv a^{n-1} \equiv 1 \pmod n$.

-Puede o no haber un elemento anterior de la secuencia que tenga un residuo 1

-Si $n$ es primo, existe un valor menor posible de $j$ ($0

-Hay dos casos a considerar

-Caso 1 ($j=0$) : Tenemos $a^{q–1} \equiv 0 \pmod n$

-Caso 2 ($1

Porque $j$ es el entero más pequeño tal que $n$ divide $(a^{2^jq}-1)$, $n$ divide $(a2^{(j+1)q}+1)$

Una prueba basada en el Teorema de Fermat ($a^{n-1} \equiv 1 \pmod n$ si $n$ es primo)

-El algoritmo es: TEST($n$) es:

1. Encontrar enteros $k$, $q$, $k > 0$, $q$ impar, tal que $(n–1)=2^kq$

2. Seleccionar un entero aleatorio $a$, 1

3. si $a^q \equiv 1 \pmod n$ entonces devolver ("quizás primo");

4. para j = 0 a k –1 hacer

5. si($a^{2^jq} \mod n = n-1$) entonces devolver(" quizás primo ")

6. devolver ("compuesto")

Answer 5

Me llevó mucho tiempo descubrirlo, pero me di cuenta de que el truco es solo un poco de factorización.

El teorema de Fermat dice que si $p$ es primo, entonces $a^{p-1} \equiv 1\ (\text{mod}\ p)$.

O en otras palabras, $a^{p-1} - 1$ está dividido por $p$ si es primo para todo $a$.

Ahora la idea detrás de la prueba de Miller-Rabin es factorizar esta expresión. Exprimes $p - 1 = 2^k d$, donde $d$ es impar.

Ahora puedes factorizar $a^{p-1} - 1 = a^{2^k d} - 1:

$a^{2^k d} - 1 = (a^{2^{k-1} d} - 1)(a^{2^{k-1} d} + 1)$

El término $a^{2^{k-1} d} - 1$ se puede factorizar aún más:

$a^{2^{k-1} d} - 1 = (a^{2^{k-2} d} - 1)(a^{2^{k-2} d} + 1)'

Y así sucesivamente. Al final tienes:

$a^{2^k d} - 1 = (a^d - 1)(a^d + 1)(a^{2d} + 1)(a^{4d} + 1)...(a^{2^{k-1}d} + 1)

Hasta ahora solo hemos factorizado la expresión y si $p$ es primo, lo dividirá.

Si $p$ es realmente primo, debe dividir al menos uno de los factores en la factorización anterior, porque debe aparecer como un factor primo en uno de estos factores (lema de Euclides).

Entonces la prueba $a^d \equiv 1\ (\text{mod}\ p)$ corresponde al primer factor. Las pruebas $a^{2^{i}d} \equiv -1\ (\text{mod}\ p)$ corresponden al resto de los factores.

Si todo es divisible por $p$, pero ninguno de los factores es divisible por $p$, entonces eso indica que los factores primos de $p$ están distribuidos entre más de un factor y ninguno de ellos lo tiene todo, lo que demuestra que $p$ es compuesto. De lo contrario, tal vez sea primo.