Algorithme de décomposition en produit de facteurs premiers
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.
Algorithme naïf
Un algorithme récursif simple, basé sur le crible d'Eratosthène, peut accomplir de telles factorisations :
Soit un nombre donné n
- si n est premier, alors la factorisation s'arrête.
- si n est composé, alors on divise n par le premier nombre premier p1
- si le reste est nul, on reprend avec la valeur n/p1 et on ajoute p1 à la liste des facteurs obtenus pour n/p1 pour avoir une factorisation pour n
- si le reste est non nul, on teste la division de n par le nombre premier suivant p2.
Il faut pour cela connaitre les nombres premiers au moins inférieurs ou égaux à √n pour marquer l'arrêt[1].
Exemple
On souhaite factoriser 9 438.
- , sans reste donc 2 est un facteur.
On reprend l'algorithme avec 4 719.
- donc 2 n'est pas un facteur.
- donc 3 est un facteur.
Le premier nombre premier par lequel 1 573 est divisible est 11.
- . De manière similaire, le nombre premier suivant qui divise 143 est 11.
- qui est lui-même premier.
Donc, en récapitulant, on a
Complexité
L'algorithme décrit ci-dessus marche bien pour les petits n, mais devient impraticable dès que n devient trop 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.
Algorithmes classiques plus efficaces
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Fairytale_warning.png/17px-Fairytale_warning.png)
Algorithmes quantiques
Références
Voir aussi
Bibliographie
Pascal Boyer, Petit compagnon des nombres et de leurs applications, Calvage et Mounet, , 648 p. (ISBN 978-2-916352-75-6), II. Nombres premiers, chap. 4 (« Factorisation »)
Articles connexes
- Théorème d'Euler
- Décomposition en produit de facteurs premiers
- Divisions successives
Lien externe
(en) Eric W. Weisstein, « Prime Factorization Algorithms », sur MathWorld
Portail de l'informatique théorique
Arithmétique et théorie des nombres