Méthode De Factorisation De Fermat


Méthode De Factorisation De Fermat

Méthode de factorisation de Fermat

En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers.

Sommaire

Intuition

L'intuition est la suivante. Tout nombre entier impair N se décompose en la différence de deux carrés : N = a2b2. Algébriquement, cette différence se factorise en (a + b)(ab) et, si ni (a + b) ni (ab) n'est égal à 1, alors ce sont des facteurs non triviaux de N.

Autrement dit, on cherche des entiers a, b tels que a2b2 (mod N). Cette relation est appelée une congruence de carrés.

Il existe une telle représentation pour tout nombre impair composé. Si N = cd est une factorisation de N, alors

N = [(c + d) / 2]2 − [(cd) / 2]2.

Puisque N est impair, c et d le sont aussi et ces « moitiés » sont des nombres entiers. (Notons qu'un multiple de 4 donne aussi une différence de deux carrés, en posant c et d comme nombres pairs.)

Dans sa forme la plus simple, la méthode de factorisation de Fermat peut être plus lente que la factorisation par essais de divisions. Néanmoins, la combinaisons des deux méthodes est plus efficace qu'uniquement l'une ou l'autre.

Méthode de base

On essaie différentes valeurs de a, en espérant que a2N = b2 soit un nombre carré.

FactorFermat(N): // N doit être impair
A ← plafond(sqrt(N))
Bsq ← A*A - N
pendant que Bsq n'est pas un carré:
A ← A + 1
Bsq ← A*A - N // ou de façon équivalente : Bsq ← Bsq + 2*A - 1
finpendant
retourner A - sqrt(Bsq) // ou A + sqrt(Bsq)

Analyse

Soit N avec plus d'une factorisation (N a plus que deux facteurs). Cette méthode produit la factorisation de N avec les plus petites valeurs de a et de b, c'est-à-dire que a + b est le plus petit facteur pas plus petit que la racine carrée de N. Donc, ab = N / (a + b) est le plus grand facteur n'excédant pas la racine carrée de N. Si la méthode produit N = 1 * N, cela montre que N est un nombre premier.

Complexité

Article détaillé : théorie de la complexité.

Pour N = cd, soit c le plus grand facteur plus petit que la racine carrée de N et soit a = (c + d) / 2. Alors, le nombre d'opérations est approximativement (c+d)/2 - \sqrt N = (\sqrt d - \sqrt c)^2 / 2 = (\sqrt N - c)^2 / 2c.

Si N est premier (donc c = 1), l'algorithme prend O(N) opérations. C'est donc une façon très inefficace de démontrer la primalité d'un nombre. Par contre, si N a un facteur suffisamment près de sa racine carrée, alors la méthode de Fermat est très efficace. Plus précisément, si c diffère de moins que {\left(4N\right)}^{1/4} de \sqrt N, la méthode ne prend qu'une seule opération. Cette analyse est indépendante de la grandeur de N.

Exemple

Par exemple, pour factoriser N = 5959, on calcule :

A: 78 79 80
Bsq: 125 282 441

Le troisième essai produit un carré. A = 80, B = 21 et les facteurs sont AB = 59 et A + B = 101.

Améliorations importantes

Les méthodes de factorisation du crible quadratique et du crible général de corps de nombres (GNFS) sont basées en grande partie sur la méthode de factorisation de Fermat.

Méthode de factorisation de Lehman

La méthode de Fermat fonctionne optimalement lorsqu'un des facteurs est approximativement la racine carrée de N. La question qui s'en suit est : peut-on s'arranger pour que ce soit le cas ?

Si on connaît approximativement le ratio de deux facteurs, d / c, alors on peut choisir un nombre rationnel, v / u, près de ce ratio. Posons Nuv = cv * du, donc les facteurs sont à peu près égaux : la méthode de Fermat appliquée à Nuv les trouvera rapidement. Puis, on obtient gcd(N,cv) = c et gcd(N,du) = d (en supposant que ce ne soit pas le cas que c divise u ou que d divise v).

En général, le ratio n'est pas connu, mais on peut essayer différentes valeurs de u / v et essayer de factoriser chaque Nuv résultant. Une méthode systématique est donnée par R. Lehman [1]. Sa complexité calculatoire est de {O} (N^{1/3 + \varepsilon}), laquelle est avantageuse par rapport à celle pour la méthodes des divisions successives, {O} (N^{1/2 + \varepsilon}).

Notes

  1. R. Lehman, "Factoring Large Integers", Mathematics of Computation, 28:637-646, 1974.

Voir aussi

Lien externe

  • Portail des mathématiques Portail des mathématiques
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « M%C3%A9thode de factorisation de Fermat ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode De Factorisation De Fermat de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Methode de factorisation de Fermat — Méthode de factorisation de Fermat En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers. Sommaire 1 Intuition 2 Méthode de base 2.1 Analyse …   Wikipédia en Français

  • Méthode de factorisation de fermat — En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers. Sommaire 1 Intuition 2 Méthode de base 2.1 Analyse …   Wikipédia en Français

  • Méthode de factorisation de Fermat — En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers. Sommaire 1 Intuition 2 Méthode de base 2.1 Analyse 2.1.1 …   Wikipédia en Français

  • Factorisation des entiers — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… …   Wikipédia en Français

  • Factorisation en nombres premiers — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… …   Wikipédia en Français

  • Factorisation entière — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… …   Wikipédia en Français

  • Factorisation entière en nombres premiers — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… …   Wikipédia en Français

  • Factorisation En Courbe Elliptique De Lenstra — La factorisation de Lenstra (par les courbes elliptiques) est un algorithme probabiliste rapide pour la décomposition en produit de facteurs premiers qui emploie les courbes elliptiques. Cette méthode fut le meilleur algorithme pour la… …   Wikipédia en Français

  • Factorisation en courbe elliptique de lenstra — La factorisation de Lenstra (par les courbes elliptiques) est un algorithme probabiliste rapide pour la décomposition en produit de facteurs premiers qui emploie les courbes elliptiques. Cette méthode fut le meilleur algorithme pour la… …   Wikipédia en Français

  • Factorisation en courbe elliptique de Lenstra — La factorisation de Lenstra (par les courbes elliptiques) est un algorithme probabiliste rapide pour la décomposition en produit de facteurs premiers qui emploie les courbes elliptiques. Cette méthode fut le meilleur algorithme pour la… …   Wikipédia en Français