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 modifier

Article détaillé : Crible d'Ératosthène.

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 à $\sqrt n$ pour marquer l'arrêt^[1].

Exemple modifier

On souhaite factoriser 9 438.

\textstyle {{\frac {9438}{2}}=4719}

, sans reste donc 2 est un facteur.

On reprend l'algorithme avec 4 719.

\textstyle {{\frac {4719}{2}}=2359,5}

donc 2 n'est pas un facteur.

\textstyle {{\frac {4719}{3}}=1573}

donc 3 est un facteur.

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

\textstyle {{\frac {1573}{11}}=143}

. De manière similaire, le nombre premier suivant qui divise 143 est 11.

\textstyle {{\frac {143}{11}}=13}

qui est lui-même premier.

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

Complexité modifier

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 modifier

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

Algorithmes quantiques modifier

Article détaillé : Algorithme de Shor.

Références modifier

(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).

↑ (en) Samuel S. Wagstaff, Jr., The Joy of Factoring, Providence, RI, AMS, coll. « Student Mathematical Library » (n^o 68), 2013, 293 p. (ISBN 978-1-4704-1048-3, présentation en ligne, lire en ligne), p. 42.

Voir aussi modifier

Bibliographie modifier

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 »)

Articles connexes modifier

Lien externe modifier

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

[1] (en) Samuel S. Wagstaff, Jr., The Joy of Factoring, Providence, RI, AMS, coll. « Student Mathematical Library » (n^o 68), 2013, 293 p. (ISBN 978-1-4704-1048-3, présentation en ligne, lire en ligne), p. 42.

[1]