¿Cómo resolver una ecuación de congruencia cuadrática de este tipo?

Question

Tengo la siguiente ecuación: $y^2 \equiv r^2 \pmod n $

Conozco los valores de y y n, sólo necesito encontrar los valores de r.

Suponiendo que $y = 12654$ y $n = 79061$ Mi trabajo es el siguiente:

$ 12654^2$ mod $79061 = r^2$ mod $79061$

$25191 = r^2$ mod $79061$

La factorización en primo de 79061 es $173*457$

Por lo tanto,

$r^2 = 25191$ mod $173$ $=>$ $106$ mod $173$

$r^2 = 25191$ mod $457$ $=>$ $56$ mod $457$

Así que ahora tengo dos ecuaciones,

$r^2 = 106$ mod $173$ y $r^2 = 56$ mod $457$

Estoy atascado aquí, agradecería si alguien puede ayudarme a avanzar.

Me he topado con otras preguntas similares en las que las respuestas muestran que se deshacen del cuadrado pero no puedo entender cómo lo hacen.

Answer 1

Usted sabe $r^2$ modulo $p$ y $q$ (los factores primos). Ahí tenemos exactamente dos soluciones: $y$ y $-y$ modulo $p$ resp. $q$ . (tenemos un campo módulo de un primo por lo que no hay más entonces $2$ ).

Ahora el CRT nos permite combinar el $4$ pares de soluciones (correspondientes a las 4 opciones posibles de signo) para $4$ solución modulo $n=pq$ .

Así, por ejemplo, resolver los sistemas $x\equiv -y \pmod p$ , $x \equiv y \pmod q$ utilizando la fórmula CRT (por ejemplo, véase wiki, prueba constructiva ) y $x\equiv y \pmod p$ , $x \equiv -y \pmod q$ para obtener las dos soluciones extra además de las ya conocidas $y$ y $-y \pmod{n} \equiv n-y$ .

Answer 2

Similar al comentario 'aleatorio' que tenemos:

$(y-r)(y+r)≡0\mod n$

$n=79061=173\times457$

Se pueden considerar los siguientes casos:

a: $y-r=173$ ⇒ $r=y-173=12654-173=12421$

b: $y+r=173$ ⇒ $r=173-12654=-12421$

Y lo hemos hecho:

$ 12654^2-(±12421)^2=55\times 79061$

c: $y-r=457$ ⇒ $r=12654+457=13111$

d: $y+r=457$ ⇒ $r=-13111$

Y lo hemos hecho:

$12654^2-13111^2=148.93...\times79061$

Así que $r= ±12421$ es aceptable.

Answer 3

La ecuación puede reescribirse como $(y-r)(y+r)=y^2 -r^2\equiv 0 \pmod n$ . Ahora cada uno de los dos factores de $n$ debe dividir al menos uno de los factores de $y^2 -r^2$ .

Answer 4

$$ 12654^2 - (91542 - 79061 m)^2 = 79061 (-79061 m^2 + 183084 m - 103968) $$ $$ r=91542 - 79061 m $$