##  [Extraction de Racine Carrée Modulaire](/fr/node/62921) 

 Définition

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

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

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

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

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

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

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 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

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.