Algorithme de décomposition en produit de facteurs premiers

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.

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