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.

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 p₁
  • si le reste est nul, on reprend avec la valeur n/p₁ et on ajoute p₁ à la liste des facteurs obtenus pour n/p₁ pour avoir une factorisation pour n
  • si le reste est non nul, on teste la division de n par le nombre premier suivant p₂.

Il faut pour cela connaitre les nombres premiers au moins inférieurs ou égaux à √n pour marquer l'arrêt^[1].

On souhaite factoriser 9 438.

${\displaystyle \textstyle {{\frac {9438}{2}}=4719}}$, sans reste donc 2 est un facteur.

On reprend l'algorithme avec 4 719.

${\displaystyle \textstyle {{\frac {4719}{2}}=2359,5}}$ donc 2 n'est pas un facteur.

${\displaystyle \textstyle {{\frac {4719}{3}}=1573}}$ donc 3 est un facteur.

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

${\displaystyle \textstyle {{\frac {1573}{11}}=143}}$. De manière similaire, le nombre premier suivant qui divise 143 est 11.

${\displaystyle \textstyle {{\frac {143}{11}}=13}}$ qui est lui-même premier.

Donc, en récapitulant, on a ${\displaystyle 9438=2\times 3\times 11\times 11\times 13=2\times 3\times 11^{2}\times 13}$

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.

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Pascal Boyer, Petit compagnon des nombres et de leurs applications, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6), II. Nombres premiers, chap. 4 (« Factorisation »)

• Théorème d'Euler
• Décomposition en produit de facteurs premiers
• Divisions successives

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

• Portail de l'informatique théorique
• Arithmétique et théorie des nombres