Algorithme de décomposition en produit de facteurs premiers

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, dans la branche de l'arithmétique modulaire, un algorithme de décomposition en produit de facteurs premiers est un algorithme (un processus pas à pas) par lequel un entier naturel est « décomposé » en un produit de facteurs qui sont des nombres premiers. Le théorème fondamental de l'arithmétique assure que cette décomposition est unique.

Description[modifier | modifier le code]

Nous pouvons décrire un algorithme récursif pour accomplir de telles factorisations : soit un nombre donné n

  • si n est premier, alors la factorisation s'arrête ici.
  • si n est composé, diviser n par le premier nombre premier p1. S'il est divisé sans reste, reprendre avec la valeur n/p1. Ajouter p1 à la liste des facteurs obtenus pour n/p1 pour avoir une factorisation pour n. S'il est divisé avec reste, diviser n par le nombre premier suivant p2, et ainsi de suite.

Notez que nous avons besoin de tester seulement les nombres premiers pi tels que pi ≤ √n.

Exemple[modifier | modifier le code]

Supposons que nous désirons factoriser 9 438.

9 438/2 = 4 719, sans reste donc 2 est un facteur.

Nous répétons l'algorithme avec 4 719.

4 719/2 = 2 359.5, donc 2 n'est pas un facteur. 4 719/3 = 1 573, donc 3 est un facteur.

Le premier nombre premier par lequel 1 573 est divisible est 11.

1 573/11 = 143. De manière similaire, le nombre premier suivant qui divise 143 est 11. 143/11 = 13. 13 est lui-même premier.

Donc, en récapitulant, nous avons 9 438 = 2×3×11×11×13 = 2×3×112×13

Complexité[modifier | modifier le code]

L'algorithme décrit ci-dessus marche bien pour les petits n, mais devient impraticable dès que n devient plus grand. Par exemple, pour un nombre de 18 chiffres décimaux, tous les nombres premiers inférieurs à 1 000 000 000 doivent être testés, ce qui prend du temps, même pour un ordinateur. À chaque fois que l'on ajoute deux chiffres au nombre à factoriser, on multiplie le temps de calcul par 10.

La difficulté de la factorisation (grande complexité en temps) en fait une base idéale pour la cryptologie moderne.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Prime Factorization Algorithms », MathWorld


(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Prime factorization algorithm » (voir la liste des auteurs).