Tonelli-Shanks Algorithm
Tonelli-Shanks calcula raíces cuadradas de residuos cuadráticos módulo un primo p: las soluciones x de x^2≡n (mod p).
Propósito
Calcular raíces cuadradas modulares para módulos primos, usado en compresión de puntos de curvas elípticas y teoría de números.
Mecanismo
Si p=2 o p≡3 (mod 4) hay solución directa. En general, escribe p-1=2^s*q, halla un no-residuo cuadrático z, fija c=z^q y ajusta iterativamente hasta que el exponente baje a 1. Complejidad O(s^2 log p).
Casos de uso
- Descompresión de puntos de curvas elípticas
- Raíces cuadradas modulares
- Algoritmos de teoría de números