Congruence de carrés

Congruence de carrés

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}~.

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.

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.



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Congruence de carrés de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Congruence De Carrés — En arithmétique modulaire, une congruence de carrés modulo un entier n est une égalité telle que . Un tel rapport porte des informations utiles dans l essai de factorisation l entier n : résoudre une congruence de carrés modulo n est un… …   Wikipédia en Français

  • Congruence de carres — Congruence de carrés En arithmétique modulaire, une congruence de carrés modulo un entier n est une égalité telle que . Un tel rapport porte des informations utiles dans l essai de factorisation l entier n : résoudre une congruence de carrés …   Wikipédia en Français

  • Nombres premiers somme de 2 carrés — Théorème des deux carrés de Fermat Pierre Fermat En mathématiques, le théorème des deux carrés de Fermat énonce les conditions pour qu’un nombre entier soit la somme de deux carrés parfaits (c est à dire de deux carrés d’entiers) et précise de… …   Wikipédia en Français

  • Theoreme des deux carres de Fermat — Théorème des deux carrés de Fermat Pierre Fermat En mathématiques, le théorème des deux carrés de Fermat énonce les conditions pour qu’un nombre entier soit la somme de deux carrés parfaits (c est à dire de deux carrés d’entiers) et précise de… …   Wikipédia en Français

  • Théorème de Fermat sur les sommes de deux carrés — Théorème des deux carrés de Fermat Pierre Fermat En mathématiques, le théorème des deux carrés de Fermat énonce les conditions pour qu’un nombre entier soit la somme de deux carrés parfaits (c est à dire de deux carrés d’entiers) et précise de… …   Wikipédia en Français

  • Théorème des deux carrés — de Fermat Pierre Fermat En mathématiques, le théorème des deux carrés de Fermat énonce les conditions pour qu’un nombre entier soit la somme de deux carrés parfaits (c est à dire de deux carrés d’entiers) et précise de combien de façons… …   Wikipédia en Français

  • Théorème des deux carrés de Fermat — Pierre Fermat En mathématiques, le théorème des deux carrés de Fermat énonce les conditions pour qu’un nombre entier soit la somme de deux carrés parfaits (c est à dire de deux carrés d’entiers) et précise de combien de façons différentes il peut …   Wikipédia en Français

  • Théorème des deux carrés de fermat — Pierre Fermat En mathématiques, le théorème des deux carrés de Fermat énonce les conditions pour qu’un nombre entier soit la somme de deux carrés parfaits (c est à dire de deux carrés d’entiers) et précise de combien de façons différentes il peut …   Wikipédia en Français

  • Théorème des quatre carrés de Lagrange — Le théorème des quatre carrés de Lagrange, est également connu sous le nom de conjecture de Bachet  ; il a été énoncé pour la première fois par Claude Gaspard Bachet de Méziriac en 1621, dans les notes accompagnant sa traduction en latin du… …   Wikipédia en Français

  • Crible Quadratique — L algorithme crible quadratique (QS pour Quadratic sieve) est un algorithme moderne de décomposition en produit de facteurs premiers fondé sur l arithmétique modulaire. Dans la pratique, la seconde méthode connue la plus rapide. C est un… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”