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 d'un entier naturel.
Intuition
L'intuition est la suivante. Tout entier naturel impair Modèle:Mvar se décompose en la différence de deux carrés : Modèle:Math. Algébriquement, cette différence se factorise en Modèle:Math et, si ni Modèle:Math ni Modèle:Math n'est égal à 1, alors ce sont des facteurs non triviaux de Modèle:Mvar.
Il existe une telle représentation pour tout nombre impair composé. Si Modèle:Mvar est une factorisation de Modèle:Mvar, alors Modèle:Retrait Puisque Modèle:Mvar est impair, Modèle:Mvar et Modèle:Mvar 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 Modèle:Mvar et Modèle:Mvar 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 combinaison des deux méthodes est plus efficace qu'uniquement l'une ou l'autre.
Méthode de base
On essaie différentes valeurs de Modèle:Mvar, en espérant que Modèle:Math soit un carré Modèle:Math. On peut utiliser qu'un carré ne peut se terminer que par 0, 1, 4, 5, 6 ou 9 dans le système décimal.
- FactorFermat(N): // N doit être impair
- A ← partie entière supérieure(√N)
- Bsq ← A×A – N
- tant que Bsq n'est pas un carré:
- A ← A + 1
- Bsq ← A×A – N // ou de façon équivalente : Bsq ← Bsq + 2×A - 1
- fin tant que
- retourner A – √(Bsq) // ou A + √(Bsq)
Analyse
Soit Modèle:Mvar un entier possédant plus d'une factorisation (Modèle:Mvar possède plus de deux facteurs). La méthode de Fermat donne la factorisation de Modèle:Mvar avec les plus petites valeurs de Modèle:Mvar et de Modèle:Mvar, c'est-à-dire que Modèle:Math est le plus petit facteur supérieur à la racine carrée de Modèle:Mvar. Donc, Modèle:Math est le plus grand facteur n'excédant pas la racine carrée de Modèle:Mvar. Si la méthode produit Modèle:Math, cela signifie que Modèle:Mvar est un nombre premier.
Complexité
Pour Modèle:Math, soit Modèle:Mvar le plus grand facteur plus petit que la racine carrée de Modèle:Mvar et soit Modèle:Math. Alors, le nombre d'itérations est approximativement Modèle:Retrait
Si Modèle:Mvar est premier (donc Modèle:Math), l'algorithme fait O(N) itérations. C'est donc une façon très inefficace de démontrer la primalité d'un nombre. Par contre, si Modèle:Mvar 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 Modèle:Mvar diffère de moins que Modèle:Math de Modèle:Sqrt, la méthode ne fait qu'une seule itération. Cette analyse est indépendante de la grandeur de Modèle:Mvar.
Exemple
Par exemple, pour factoriser Modèle:Math (Modèle:Math), on calcule :
| A | 78 | 79 | 80 |
|---|---|---|---|
| Bsq | 125 | 282 | 441 |
Le troisième essai produit un carré : Modèle:Math et les facteurs sont Modèle:Math et Modèle:Math.
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
Modèle:Article détaillé La méthode de Fermat fonctionne optimalement lorsqu'un des facteurs est approximativement la racine carrée de Modèle:Mvar. La question qui s'ensuit est : peut-on s'arranger pour que ce soit le cas ?
Si on connaît approximativement le quotient de deux facteurs, Modèle:Math, alors on peut choisir un nombre rationnel, Modèle:Math, proche de ce quotient. Posons Modèle:Math, donc les facteurs sont à peu près égaux : la méthode de Fermat appliquée à Modèle:Mvar les trouvera rapidement. Puis, on obtient Modèle:Math et Modèle:Math (sauf si Modèle:Mvar divise Modèle:Mvar ou Modèle:Mvar divise Modèle:Mvar).
En général, le quotient n'est pas connu, mais on peut essayer différentes valeurs de Modèle:Math et essayer de factoriser chaque Modèle:Mvar résultant. Une méthode systématique est donnée par Russell Sherman Lehman[1]. Sa complexité calculatoire est de Modèle:Math, laquelle est avantageuse par rapport à celle pour la méthode des divisions successives, dont la complexité est en Modèle:Math.
Notes et références
Modèle:Traduction/Référence Modèle:Références