Le processus de trouver des entiers x tels que x^2 ≡ a (mod n) lorsque de telles solutions existent ; c'est‑à‑dire extraire des racines carrées dans l'anneau Z/nZ ou dans ses facteurs locaux quand n est composé.

Principe

La solvabilité dépend du fait que a soit un résidu quadratique modulo chaque puissance première divisant n ; pour un module premier p on utilise Tonelli–Shanks (si p impair) ou une inspection pour p=2 ; pour les puissances premières on applique le relèvement de Hensel ; pour n composé la factorisation plus la recombinaison par CRT ramènent le problème aux cas de puissances premières.

Démonstration

Exemple : trouver x tel que x^2 ≡ 10 (mod 13). Les carrés modulo 13 montrent 6^2 = 36 ≡ 10 et 7^2 = 49 ≡ 10, donc x ≡ 6 ou 7 (mod 13). Pour n composé, factoriser n, résoudre chaque congruence modulo puissance première, et recombiner par le théorème des restes chinois pour obtenir toutes les solutions modulo n.

Mauvaise application

Supposer à tort qu'une racine carrée existe modulo un module composé sans vérifier la résiduité quadratique pour chaque facteur premier, ou tenter une recombinaison CRT sans solutions locales compatibles ; traiter Tonelli–Shanks comme applicable sans vérifier les conditions sur p est une mauvaise pratique.

Conséquence

Une extraction correcte donne des classes de racines explicites employées en tests de primalité, protocoles cryptographiques (et attaques), et pour résoudre des congruences quadratiques et relever des solutions à des modules supérieurs.

Inversion

Le point de vue inverse est la décision de la résiduité quadratique (si a est un carré modulo n) plutôt que la construction des racines ; lorsque la décision de résiduité est difficile (p. ex. n composé sans factorisation), l'extraction devient infaisable et la résiduité devient la question centrale.

Limite

S'applique aux congruences quadratiques x^2 ≡ a (mod n) et dépend de la structure factorielle de n ; exclut l'extraction générale de k‑èmes racines sauf adaptation, et peut être en pratique infaisable sans factorisation de n composé.

Tension sémantique

Tension entre le travail sur corps premiers F_p (où l'anneau est un corps et les algorithmes standards s'appliquent) et les modules composés Z/nZ (non corps) : le premier admet inversion algébrique directe, le second exige factorisation et CRT ou conduit à ambiguïtés si les facteurs sont inconnus.

Synthèse

L'extraction de racines carrées modulaires consiste à vérifier la résiduité quadratique aux puissances premières locales, calculer des racines locales (Tonelli–Shanks, relèvement de Hensel) et recombiner par le théorème des restes chinois pour produire toutes les solutions entières x modulo n lorsque celles‑ci existent.