Calcul d’un résidu quadratique
Testez si un entier a est un résidu quadratique modulo n, trouvez les solutions de l’équation x² ≡ a (mod n) et visualisez la distribution des carrés modulo n.
Paramètres du calcul
Entier à tester dans la congruence x² ≡ a (mod n).
Utilisez un entier positif n ≥ 2. Pour un calcul fluide, gardez n raisonnable.
Le mode exploration met surtout l’accent sur la liste complète des carrés modulo n.
Limite d’affichage pour les listes de solutions et de résidus.
Si n est un nombre premier impair, le symbole de Legendre via le critère d’Euler peut être affiché.
Visualisation des carrés modulo n
Le graphique montre, pour chaque résidu r entre 0 et n-1, combien de valeurs de x vérifient x² ≡ r (mod n). Pour un module premier impair, les résidus quadratiques non nuls apparaissent typiquement avec 2 antécédents, tandis que les non-résidus ont 0 antécédent.
Guide expert du calcul d’un résidu quadratique
Le calcul d’un résidu quadratique fait partie des outils fondamentaux de la théorie des nombres. Derrière ce nom un peu technique se cache une idée simple : on cherche à savoir si un entier donné peut s’écrire comme un carré parfait dans l’arithmétique modulaire. Plus précisément, pour un entier a et un module n, on demande s’il existe un entier x tel que x² ≡ a (mod n). Si une telle solution existe, alors a est appelé un résidu quadratique modulo n. Sinon, on parle de non-résidu quadratique.
Cette notion n’est pas seulement théorique. Elle intervient dans les algorithmes de cryptographie, dans les tests de primalité, dans l’étude des congruences et dans de nombreux protocoles de sécurité. Lorsqu’on manipule des systèmes modulaires, comprendre les résidus quadratiques permet de prévoir l’existence de racines carrées modulo un entier, d’analyser la structure d’un groupe multiplicatif et d’optimiser certaines méthodes de calcul.
Définition rapide : un entier a est un résidu quadratique modulo n s’il existe au moins un entier x pour lequel x² mod n = a mod n. Le calcul pratique consiste donc à normaliser a, puis à étudier les valeurs prises par x² modulo n.
Pourquoi le sujet est important
La raison principale est que les carrés modulo un entier ne couvrent pas toujours toutes les classes de résidus. Par exemple, modulo 11, les carrés ne produisent pas les valeurs 2, 6, 7, 8 ou 10 comme classes de résidus. Cela signifie qu’aucune équation de la forme x² ≡ 2 (mod 11) n’a de solution. Cette propriété est essentielle dans les schémas cryptographiques fondés sur la difficulté de calculer des racines carrées modulaires, notamment lorsque le module est composite et bien choisi.
En pratique, trois tâches reviennent souvent :
- déterminer si une valeur est un résidu quadratique modulo un nombre donné ;
- énumérer toutes les valeurs atteignables sous la forme x² mod n ;
- trouver toutes les solutions de la congruence x² ≡ a (mod n).
Comment effectuer le calcul d’un résidu quadratique
1. Normaliser la valeur de a
La première étape consiste à réduire a modulo n. Par exemple, si vous étudiez a = 38 modulo 11, vous pouvez remplacer 38 par 5, puisque 38 ≡ 5 (mod 11). Cela simplifie le problème sans rien changer à la réponse.
2. Calculer les carrés modulo n
Ensuite, on calcule les valeurs de x² mod n pour x = 0, 1, 2, …, n-1. Dès qu’une valeur correspond à a mod n, on sait que a est un résidu quadratique. Cette méthode par balayage exhaustif est très fiable et parfaitement adaptée aux calculs pédagogiques, aux petits modules et aux outils interactifs.
3. Identifier les solutions
Quand on trouve des solutions, il est utile de toutes les lister. Pour un module premier impair p, un résidu quadratique non nul possède généralement deux racines distinctes : x et p – x. En revanche, la classe 0 n’a qu’une seule racine, à savoir 0. Pour un module composite, la structure peut être plus riche, avec parfois 0, 2, 4 ou davantage de solutions selon la décomposition de n.
Exemple direct : modulo 11
Calculons les carrés modulo 11 :
- 0² ≡ 0
- 1² ≡ 1
- 2² ≡ 4
- 3² ≡ 9
- 4² ≡ 5
- 5² ≡ 3
- 6² ≡ 3
- 7² ≡ 5
- 8² ≡ 9
- 9² ≡ 4
- 10² ≡ 1
On obtient donc l’ensemble des résidus quadratiques modulo 11 : {0, 1, 3, 4, 5, 9}. Si l’on veut tester a = 5, la réponse est oui, et les solutions sont x ≡ 4 et x ≡ 7 (mod 11).
| Module n | Résidus quadratiques distincts | Nombre de résidus distincts | Observation |
|---|---|---|---|
| 5 | {0, 1, 4} | 3 | Pour un nombre premier p = 5, on obtient (p + 1) / 2 = 3 résidus distincts. |
| 7 | {0, 1, 2, 4} | 4 | Comme prévu pour p = 7, il y a 4 résidus distincts en incluant 0. |
| 8 | {0, 1, 4} | 3 | Les modules composés peuvent donner une distribution moins régulière. |
| 9 | {0, 1, 4, 7} | 4 | La présence d’une puissance de 3 modifie le nombre de classes atteignables. |
| 11 | {0, 1, 3, 4, 5, 9} | 6 | Pour p = 11, on retrouve (11 + 1) / 2 = 6 résidus distincts. |
| 13 | {0, 1, 3, 4, 9, 10, 12} | 7 | La moitié environ des classes non nulles sont des carrés modulo 13. |
| 15 | {0, 1, 4, 6, 9, 10} | 6 | Avec un module composite, le comportement dépend des facteurs premiers de n. |
Le cas des nombres premiers impairs
Quand le module p est un nombre premier impair, la théorie devient particulièrement élégante. Il existe exactement (p – 1) / 2 résidus quadratiques non nuls, auxquels s’ajoute 0 si l’on compte toutes les classes. Cette symétrie vient du fait que x² ≡ (-x)² (mod p). Les valeurs non nulles se regroupent donc naturellement par paires.
Dans ce contexte, un critère majeur s’appelle le critère d’Euler. Il affirme que pour tout entier a non divisible par p :
- si a^((p-1)/2) ≡ 1 (mod p), alors a est un résidu quadratique ;
- si a^((p-1)/2) ≡ -1 (mod p), alors a est un non-résidu quadratique.
Ce test évite de parcourir toutes les valeurs de x. Il est extrêmement utile dès que le module devient plus grand. Dans un calculateur pédagogique, on peut cependant conserver l’énumération complète parce qu’elle permet d’afficher les solutions exactes et de produire un graphique interprétable immédiatement.
Symbole de Legendre
Le symbole de Legendre, noté (a/p), résume le statut quadratique de a modulo un premier impair p. Il vaut :
- 0 si p divise a ;
- 1 si a est un résidu quadratique modulo p ;
- -1 sinon.
Ce symbole est central dans les démonstrations et les algorithmes. Il sert de passerelle entre le calcul modulaire élémentaire et des résultats plus profonds comme la loi de réciprocité quadratique.
Tableau statistique détaillé pour le module 11
Le tableau suivant récapitule, pour chaque classe modulo 11, le nombre de solutions à l’équation x² ≡ a (mod 11). Les chiffres sont exacts et proviennent de l’énumération complète des carrés modulo 11.
| Valeur a modulo 11 | Nombre de solutions | Solutions x modulo 11 | Statut |
|---|---|---|---|
| 0 | 1 | {0} | Résidu quadratique |
| 1 | 2 | {1, 10} | Résidu quadratique |
| 2 | 0 | Aucune | Non-résidu |
| 3 | 2 | {5, 6} | Résidu quadratique |
| 4 | 2 | {2, 9} | Résidu quadratique |
| 5 | 2 | {4, 7} | Résidu quadratique |
| 6 | 0 | Aucune | Non-résidu |
| 7 | 0 | Aucune | Non-résidu |
| 8 | 0 | Aucune | Non-résidu |
| 9 | 2 | {3, 8} | Résidu quadratique |
| 10 | 0 | Aucune | Non-résidu |
Modules composés : pourquoi c’est plus subtil
Lorsque n n’est pas premier, la situation devient plus nuancée. La condition d’être un carré modulo n dépend de la structure factorisée du module. Par exemple, pour n = 15, on travaille implicitement avec les comportements modulo 3 et modulo 5. Le théorème chinois des restes explique alors pourquoi certaines classes ont des solutions et pourquoi le nombre de racines peut augmenter.
Dans un module composite, il ne faut donc pas supposer qu’un résidu quadratique non nul aura exactement deux racines. Il peut y en avoir davantage. C’est une des raisons pour lesquelles les schémas cryptographiques basés sur des modules composites soigneusement choisis peuvent être très intéressants du point de vue de la sécurité.
Bonnes pratiques de calcul
- toujours réduire d’abord a modulo n ;
- vérifier si n est premier avant d’utiliser des critères spécialisés ;
- pour les petits modules, l’énumération complète est simple et sans ambiguïté ;
- pour les grands modules premiers, le critère d’Euler est souvent plus efficace ;
- pour les modules composites, l’analyse des facteurs premiers peut être déterminante.
Méthodes algorithmiques courantes
Énumération complète
C’est la méthode la plus directe : on calcule x² mod n pour chaque x entre 0 et n-1. Elle est idéale pour l’enseignement, les démonstrations, les tableaux de distribution et les modules de taille modérée.
Critère d’Euler
Réservé au cas où n = p est un premier impair. Cette approche remplace la recherche exhaustive par une exponentiation modulaire rapide. Elle est très efficace pour tester le statut quadratique d’une valeur.
Algorithmes de racine carrée modulaire
Une fois qu’on sait qu’un résidu quadratique existe modulo un premier, des algorithmes comme Tonelli-Shanks permettent de calculer effectivement une racine carrée modulaire. C’est une étape centrale dans plusieurs applications cryptographiques avancées.
Applications concrètes
Les résidus quadratiques apparaissent dans :
- les protocoles de preuve à divulgation nulle de connaissance ;
- certaines constructions cryptographiques historiques ;
- la génération de pseudo-aléa fondée sur l’arithmétique modulaire ;
- la résolution de congruences polynomiales ;
- l’étude de la répartition des carrés dans les corps finis.
Pour approfondir, vous pouvez consulter des ressources universitaires et institutionnelles de qualité, notamment les notes de théorie des nombres du MIT, l’introduction de Stanford sur les résidus quadratiques à l’adresse stanford.edu, ainsi que des supports de cours de cryptographie mathématique publiés par Clemson University.
Comment interpréter le graphique du calculateur
Le graphique de cette page associe à chaque résidu possible r le nombre de solutions de x² ≡ r (mod n). Cette représentation est particulièrement informative :
- si la barre est nulle, alors r n’est pas un résidu quadratique ;
- si la barre est positive, alors r est atteignable comme carré modulo n ;
- pour un module premier impair, les résidus non nuls ont souvent une hauteur égale à 2 ;
- pour un module composite, des hauteurs différentes peuvent apparaître, révélant une structure plus complexe.
Erreurs fréquentes à éviter
- confondre un carré entier ordinaire avec un carré modulo n ;
- oublier de réduire les valeurs négatives ou très grandes modulo n ;
- appliquer le critère d’Euler à un module qui n’est pas premier ;
- penser qu’un résidu quadratique a toujours exactement deux racines ;
- oublier que la classe 0 a un comportement particulier.
Conclusion
Le calcul d’un résidu quadratique relie calcul concret, visualisation et théorie profonde. Avec un simple test de congruence, on peut identifier si une valeur est représentable comme carré modulo un entier, trouver ses racines éventuelles et comprendre la structure du système modulaire étudié. Pour les petits modules, l’énumération exhaustive reste la méthode la plus transparente. Pour les grands nombres premiers, les critères algorithmiques accélèrent considérablement le travail. Dans tous les cas, le concept est indispensable à toute personne qui souhaite maîtriser l’arithmétique modulaire, la théorie des nombres élémentaire et une partie importante de la cryptographie moderne.