¿Cómo se resuelve $x*x = 1009732533765288 \mod 1009732533765289$ ?

Question

¿Cómo se resuelve $x*x = 1009732533765288 \mod 1009732533765289$ ? Wolframalpha cuando se conecta eso tiene las respuestas como:

$x \equiv 389427288088687 \mod 1009732533765289$

y

$x \equiv 620305245676602 \mod 1009732533765289$

ambos de $389427288088687 + 620305245676602 = 1009732533765289$ . Me pregunto cómo las resuelve para poder escribir un programa que resuelva este tipo de ecuaciones. Gracias.

Answer 1

Voy a utilizar el hecho de que el número es impar para evitar tecnicismos. Dado que su número tiene un tamaño aproximado de $10^{15}$ se puede calcular de varias maneras.

Se podría entonces resolver para cada $p^k$ . Para ello se puede encontrar una raíz primitiva $r$ en la forma normal y sólo dejar que $x=r^{(p-1)p^k/4}$ o $x=r^{3(p-1)p^k/4}$ (no hay solución si $p$ no es congruente con $1\bmod 4$ ).

Entonces se puede utilizar el teorema chino del resto para encontrar una solución que funcione para todos los primos simultáneamente.

Si el número es par hacemos lo siguiente: Si el número es múltiplo de $4$ no hay solución, y si el número no es múltiplo de $4$ entonces sólo asegúrate de que el número que obtienes al final con CRT es impar y ya estamos listos.