Algorithme de decomposition en produit de facteurs premiers

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 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 simple algorithme de factorisation

Description

Nous pouvons décrire un algorithme récursif pour accomplir de telles factorisations : soit un nombre donné n

• si n est premier, alors la factorisation s'arrête ici.
• si n est composé, diviser n par le premier nombre premier p₁. S'il est divisé sans reste, reprendre avec la valeur n/p₁. Ajouter p₁ à la liste des facteurs obtenus pour n/p₁ pour avoir une factorisation pour n. S'il est divisé avec reste, diviser n par le nombre premier suivant p₂, et ainsi de suite.

Notez que nous avons besoin de tester seulement les nombres premiers p_i tels que p_i ≤ √n.

Exemple

Supposons que nous désirons factoriser 9 438.

9 438/2 = 4 719, sans reste donc 2 est un facteur.

Nous répétons l'algorithme avec 4 719.

4 719/2 = 2 359.5, donc 2 n'est pas un facteur. 4 719/3 = 1 573, donc 3 est un facteur.

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

1 573/11 = 143. De manière similaire, le nombre premier suivant qui divise 143 est 11. 143/11 = 13. 13 est lui-même premier.

Donc, en récapitulant, nous avons 9 438 = 2×3×11×11×13 = 2×3×11²×13

Voici l'exemple en python :

import math,sys
def factorize(n):
    def isPrime(n):
        return not [x for x in xrange(2,int(math.sqrt(n)) + 1)
                    if n%x == 0]
    primes = []
    candidates = xrange(2,n+1)
    candidate = 2
    while not primes and candidate in candidates:
        if n%candidate == 0 and isPrime(candidate):
            primes.append(candidate)
            primes = primes + factorize(n/candidate)
        candidate += 1            
    return primes
print factorize(int(sys.argv[1]))

Sortie :

python factorize.py 9438
[2, 3, 11, 11, 13]

Complexité

L'algorithme décrit ci-dessus marche bien pour les petits n, mais devient impraticable dès que n devient plus grand. Par exemple, pour un nombre de 18 chiffres décimaux (ou 60 chiffres bits), tous les nombres premiers inférieurs à 1 000 000 000 doivent être testés, ce qui devient long, même pour un ordinateur. En ajoutant deux chiffres décimaux au nombre original, on multiplie le calcul par 10.

La difficulté de la factorisation (complexité en temps large) en fait une base idéale pour la cryptologie moderne.

Voir aussi : Théorème d'Euler, Décomposition en produit de facteurs premiers, Essais de divisions

Lien externe

• (en) Prime factorization at Mathworld

Ce document provient de « Algorithme de d%C3%A9composition en produit de facteurs premiers ».