Tonelli-Shanks Algorithm
Tonelli-Shanks calcule les racines carrées des résidus quadratiques modulo un nombre premier p : les solutions x de x^2≡n (mod p).
Objectif
Calculer des racines carrées modulaires pour des modules premiers, utilisé dans la compression de points de courbes elliptiques et en théorie des nombres.
Mécanisme
Si p=2 ou p≡3 (mod 4), il existe une solution directe. En général, on écrit p-1=2^s*q, on trouve un non-résidu quadratique z, on pose c=z^q et l'on ajuste itérativement jusqu'à ce que l'exposant descende à 1. Complexité O(s^2 log p).
Cas d’usage
- Décompression de points de courbes elliptiques
- Racines carrées modulaires
- Algorithmes de théorie des nombres