El algoritmo propuesto jugar un juego de cara o cruz por teléfono dado aquí afirma que el saber las cuatro soluciones a $$ x^2 \equiv a^2 \pmod n$$ would allow us to factor $n$ where $n$ is a product of two unknown primes $p,q$ and $\gcd (a, n) = 1$. Sin embargo, no veo por qué esto sería cierto. ¿Puede alguien explicarme por favor?
Respuestas
¿Demasiados anuncios?
Que $a_p$ ser una raíz cuadrada de $a$ modulo $p$, y que $a_q$ ser una raíz cuadrada de $a$ modulo $q$. Las cuatro raíces cuadradas son dados por números $x,y,z,w$ tal que:
- $x \equiv a_p \pmod{p}$ y $x \equiv a_q \pmod{q}$.
- $y \equiv a_p \pmod{p}$ y $y \equiv -a_q \pmod{q}$.
- $z \equiv -a_p \pmod{p}$ y $z \equiv a_q \pmod{q}$.
- $w \equiv -a_p \pmod{p}$ y $w \equiv -a_q \pmod{q}$.
Si nos fijamos en $x-y$, por ejemplo, y encontrará la que $x-y \equiv 0 \pmod{p}$ y $x-y \equiv 2a_q \pmod{q}$. Esto significa que el $x-y$ es divisible por $p$ pero no por $q$ y así $\mathrm{gcd}(x-y,n) = p$.
Oli
Puntos
89
Las cuatro soluciones son de la forma $x\equiv \pm b\pmod{pq}$ y $x\equiv \pm c\pmod{pq}$.
Existen sólo dos soluciones modulo $p$. Así $b\equiv \pm c\pmod{p}$. Se sigue que sea $b-c\equiv 0\pmod{p}$ o $b+c\equiv 0\pmod{p}$.
Así uno de #% de %#% o $\gcd(m,b-c)$ es igual a $\gcd(m,b+c)$, y el otro es igual a $p$. Puede computar el gcd barato usando el Algoritmo euclidiano.
David HAust
Puntos
2696
% Toque $\ $nos podemos dividir $\rm n>1\,$ en factores no triviales por un cálculo rápido gcd si nos dan un polinomio distinto de cero tiene más raíces $\,r_i\,$mod $\rm\, n\,$ de su grado. Es decir, uno de $\,\gcd(n,\,r_i-r_j),\ i\neq j\,$ rinde un adecuado factor de $\,n.\,$ aquí para más detalles.
