Congruence de carrés (encyclopédie mathématiques)

En arithmétique modulaire, une congruence de carrés modulo un entier n est une équation de la forme

$x^2\equiv y^2 \pmod{n}\qquad\hbox{avec}\qquad x\not\equiv \pm y\pmod{n}~.$

[modifier] Utilisation

Une telle équation apporte des informations utiles pour essayer de factoriser l'entier n. En effet,

$x^2\equiv y^2\pmod{n}\quad\Rightarrow\quad x^2-y^2\equiv 0\pmod{n}\quad\Rightarrow\quad (x+y)(x-y)\equiv 0\pmod{n}~.$

Ceci veut dire que n divise le produit (x+y)(x−y) mais ne divise aucun des deux facteurs x+y et x−y, donc x+y et x−y contiennent tous les deux des diviseurs propres de n, que l'on trouve en calculant les PGCD de (x +y, n) et de (x−y,n). La difficulté n'est donc pas d'exploiter une telle congruence mais d'en trouver une, c'est-à-dire de trouver un tel couple (x,y).

Ce type de congruence est un prolongement de la méthode de factorisation de Fermat. Il est utilisé dans de nombreuses méthodes de factorisation comme le crible quadratique, le crible de corps de nombres et la factorisation de Dixon. Cette approche de la factorisation montre aussi que le problème de la factorisation de n peut être réduit au problème de recherche de racines carrées modulo n.

[modifier] Exemple

Soit n = 35. On a

$\textstyle 6^2 \equiv 36 \equiv 1 \equiv 1^2 \pmod{n}\qquad\hbox{mais}\qquad 6\not\equiv \pm 1\pmod{n}$ .

Ceci permet de factoriser 35 sous forme du produit de pgcd(6 − 1, 35) = 5 par pgcd(6 + 1, 35) = 7.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Congruence of squares » (voir la liste des auteurs)

Congruence de carrés

[modifier] Utilisation

[modifier] Exemple

Rechercher

Menu

Espace membre

Changer d'île