Algoritmo determinista para calcular una raíz cuadrada de un residuo cuadrático a módulo un primo impar p (encontrar x con x^2 ≡ a (mod p)) mediante exponentiaciones y ajustes iterativos usando la descomposición p−1 = q·2^s y un no-residuo cuadrático.

Principio

Reducir la búsqueda de la raíz a exponentiaciones repetidas y correcciones multiplicativas controladas: escribir p−1 = q·2^s con q impar, hallar un no-residuo cuadrático z, formar el candidato inicial a^{(q+1)/2} y corregir iterativamente con potencias de z para eliminar obstrucciones 2-ádicas hasta producir una raíz cuadrada real.

Demostración

Ejemplo: para p = 11 y a = 3, el algoritmo comprueba que 3 es residuo cuadrático, elige z = 2 como no-residuo, escribe p−1 = 10 = 5·2^1, calcula el candidato a^{(q+1)/2} = 3^{3} ≡ 5 (mod 11) y verifica que 5^2 ≡ 3, luego x = 5 (y 6) son raíces; el procedimiento se generaliza a primos mayores por la misma secuencia de exponentiaciones y correcciones.

Aplicación incorrecta

Aplicarlo sin cambio a un módulo compuesto n o en p = 2, o usarlo cuando a no es residuo cuadrático, causa fallo; omitir la descomposición 2-ádica o elegir un z que en realidad sea residuo produce resultados erróneos.

Consecuencia

Bien aplicado, produce una raíz cuadrada legítima módulo un primo impar y constituye un método determinista y práctico empleado en rutinas de aritmética modular (por ejemplo, descompresión de puntos en curvas elípticas o algoritmos que necesitan raíces modulares).

Inversión

La perspectiva inversa es partir de un candidato x y comprobar x^2 mod p para certificar a; alternativamente, la incapacidad de producir una raíz permite, mediante el símbolo de Legendre, afirmar la ausencia de raíz. Como contraste, para primos con p ≡ 3 (mod 4) existe a menudo el atajo x = a^{(p+1)/4}.

Límite

Solo definido para módulos primos impares p y para entradas a que sean residuos cuadráticos módulo p; no es aplicable a módulos compuestos generales sin modificación y requiere la existencia de un no-residuo cuadrático módulo p para efectuar las correcciones.

Tensión semántica

Compite con otros métodos de raíz cuadrada modular como el algoritmo de Cipolla (usa una extensión cuadrática) o atajos de exponenciación para primos especiales; las compensaciones incluyen determinismo, factores constantes y facilidad de implementación.

Síntesis

Tonelli–Shanks es un método determinista y estructurado que transforma el problema de hallar raíces cuadradas modulares en una secuencia controlada de exponentiaciones y correcciones multiplicativas basada en la descomposición 2-ádica de p−1 y un no-residuo elegido, produciendo una raíz cuando existe.