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 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 à Modèle:Sqrt pour marquer l'arrêt<ref>Modèle:Ouvrage.</ref>.

Exemple

On souhaite factoriser 9 438.

<math>\textstyle{\frac{9438}2 = 4719}</math>, sans reste donc 2 est un facteur.

On reprend l'algorithme avec 4 719.

<math>\textstyle{\frac{4719}2 = 2359,5}</math> donc 2 n'est pas un facteur.

<math>\textstyle{\frac{4719}3 = 1573}</math> donc 3 est un facteur.

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

<math>\textstyle{\frac{1573}{11} = 143}</math>. De manière similaire, le nombre premier suivant qui divise 143 est 11.

<math>\textstyle{\frac{143}{11} = 13}</math> qui est lui-même premier.

Donc, en récapitulant, on a <math>9438 = 2\times 3\times 11 \times 11 \times 13 = 2 \times 3 \times 11^2 \times 13</math>

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.

Voir aussi

Articles connexes

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