Miller-Rabin: Mostrando divisores no triviales de $n$

Question

Supongamos que $n$ no pasa la prueba Miller-Rabin y $b$ es un testigo. Significado, $b^{\frac{n-1}{2^r}} \equiv 1 \pmod{n}$ donde $\frac{n-1}{2^r}$ es par, pero $c = b^{\frac{n-1}{2^{r+1}}} \not\equiv \pm1 \pmod{n}$ . Demostrar que $\gcd(c+1,n),\gcd(c-1, n)$ son divisores no triviales de $n$ .

Así que, en primer lugar, para mi comodidad:

• Denote $n-1 = 2^ls$ , $s$ es impar.
• Denote $k=l-r$ .
  • $c = b^{2^{k-1}s}$
  • $c^2 = b^{2^{k}s}$
  • $2^ks$ es incluso

Se da que $c^2 \equiv 1 \pmod{n} \implies (c-1)(c+1) \equiv 0 \pmod {n} \implies n\mid (c-1)(c+1)$

Ahora, Creo que podemos suponer que $n$ ha pasado la prueba del teorema de Fermat (que forma parte de las pruebas iniciales del algoritmo Miller-Rabin).

Por lo tanto,

$$c^{r+1} = b^{2^l s} = b^{n-1} \equiv 1 \pmod {n}$$

pero eso no revela nada nuevo más que $r$ es impar (ya que $2$ debe dividir $r+1$ ).

¿Qué me falta?

Answer 1

La afirmación general es que siempre que tengamos una raíz cuadrada no trivial de $1$ modulo $n$ , un valor $c$ tal que $$ c^2 \equiv 1 \pmod{n}, \qquad c \not\equiv \pm1 \pmod{n}, $$ entonces obtenemos una factorización de $n$ .

Si $c^2 \equiv 1 \pmod n$ entonces $(c+1)(c-1) \equiv 0 \pmod n$ .

Si $c+1$ eran relativamente primos a $n$ entonces tendría un módulo inverso $n$ y podríamos multiplicar por $(c+1)^{-1}$ para concluir que $c-1 \equiv 0 \pmod n$ . Pero esto queda descartado por nuestra suposición de que $c \not\equiv 1 \pmod n$ .

Si $c+1$ eran divisibles por $n$ entonces tendríamos $c+1 \equiv 0 \pmod n$ . Pero esto queda descartado por nuestra suposición de que $c \not\equiv -1 \pmod n$ .

Así que la única posibilidad que queda es que $c+1$ comparte algunos factores primos, pero no todos, con $n$ que $\gcd(c+1,n)$ es un factor no trivial de $n$ .

Lo mismo ocurre con el otro factor $c-1$ .

---

De forma más general, siempre que encontremos $a$ y $b$ tal que $a^2 \equiv b^2 \pmod n$ pero $a \not\equiv \pm b \pmod n$ el mismo argumento muestra que $\gcd(a+b,n)$ y $\gcd(a-b,n)$ son factores no triviales de $n$ . Esta es la base de muchos algoritmos de factorización de enteros a partir de Método de factorización de Fermat y terminando con el tamiz cuadrático .

Answer 2

Desde $b^{\frac{n-1}{2^r}}\equiv 1\pmod n$ vemos que existe un número entero $m$ tal que $$b^{\frac{n-1}{2^r}}=mn+1\tag1$$ Desde $b^{\frac{n-1}{2^{r+1}}}\not\equiv \pm 1\pmod n$ vemos que existen enteros $k,r$ tal que $$b^{\frac{n-1}{2^{r+1}}}=kn+r+1\tag2$$ donde $$\text{$ 1 \le r \le n-1 \quad$ with $\quad r \not =n-2 $}\tag3$$

Desde $\frac{n-1}{2^r}$ es par, obtenemos, de $(1)(2)$ , $$mn+1=b^{\frac{n-1}{2^r}}=b^{\frac{n-1}{2^{r+1}}\times 2}=\left(b^{\frac{n-1}{2^{r+1}}}\right)^2=(kn+r+1)^2=(k^2n+2kr+2k)n+(r+1)^2$$ que implica $$1\equiv (r+1)^2\equiv r^2+2r+1\pmod n$$ lo que implica $$r(r+2)\equiv 0\pmod n\tag4$$

Aquí, suponiendo que $r+2=n+1$ implica $r\equiv 0\pmod n$ que es imposible.

Así, desde $(3)$ tenemos $1\lt r\lt n$ y $1\lt r+2\lt n$ .

De esto y de $(4)$ que ambos $r$ y $r+2$ son divisores no triviales de $n$ .

Tenemos $b^{\frac{n-1}{2^{r+1}}}+1=kn+r+2$ . Desde $r+2$ es un divisor no trivial de $n$ vemos que $\gcd\left(b^{\frac{n-1}{2^{r+1}}} +1,n\right)$ es un divisor no trivial de $n$ .

Tenemos $b^{\frac{n-1}{2^{r+1}}}-1=kn+r$ . Desde $r$ es un divisor no trivial de $n$ vemos que $\gcd\left(b^{\frac{n-1}{2^{r+1}}} -1,n\right)$ es un divisor no trivial de $n$ .