Encuentra el entero positivo mínimo $x$ tal que $x^2 \equiv 30 \pmod{101}$

Question

Encuentra el entero positivo más pequeño $x$ tal que $x^2 \equiv 30 \pmod{101}$

Es la primera vez que me encuentro con este tipo de problema, he buscado en Internet pero no obtuve resultados. ¿Existe una fórmula o un algoritmo para resolver este tipo de problemas? ¡Agradecería mucho tu apoyo!

Answer 1

El enfoque "fuerza bruta" sería probar cada $x$ desde $1$ hasta $101$. Podemos estar seguros de que no tendremos que probar valores más grandes de $x$, porque si $x \equiv y \pmod{101}$, entonces $x^2 \equiv y^2 \pmod{101}$.

Aquí hay un enfoque menos tedioso que se basa en el hecho de que $101$ es primo y $101 \equiv 5 \pmod{8}$. Una prueba de la siguiente afirmación se puede encontrar en la sección 1.5 de este libro de texto.

Afirmación: Supongamos que $p$ es un primo con $p \equiv 5 \pmod{8}$, y supongamos que $x^2 \equiv a \pmod{p}$. Entonces $x \equiv \pm a^{(p + 3)/8} \pmod{p}$ o $x \equiv \pm 2a \cdot (4a)^{(p - 5)/8} \pmod{p}$.

En nuestro caso, $p = 101$ y $a = 30$. Puedes calcular rápidamente los valores $a^{(p + 3)/8}$ y $2a \cdot (4a)^{(p - 5)/8}$ módulo $101$ utilizando el método de exponenciación por cuadrados.

Si estuviéramos trabajando módulo algún otro primo $p$, el algoritmo Tonelli-Shanks sería un buen enfoque. ¿Qué pasaría si estuviéramos trabajando módulo un número compuesto grande $n$? Se presume que no existe un algoritmo eficiente para resolver una ecuación dada de la forma $x^2 \equiv a \pmod{n}$. Un algoritmo eficiente para ese problema podría usarse para factorizar grandes números enteros y así romper sistemas criptográficos importantes como RSA.