Pour la définition de ce qu'est un nombre premier, voir ici: http://fr.wikipedia.org/wiki/Nombre_premier

On peut toujours décomposer un nombre entier quelconque en facteurs premiers.

Par exemple: facteurs(50) ⇒ 2*5*5

Bien entendu, un nombre premier ne trouve que lui-même comme facteur premier!

Le principe du calcul est assez trivial, et consiste à faire des divisions entières systématiques avec divmod(). Cette fonction renvoie une liste de 2 valeurs: le résultat de la division entière et son reste. Si le reste est nul, c'est que la division est exacte, et on a trouvé un facteur de plus. On l'ajoute à la liste F, on remplace le n précédent par le résultat de cette division, et on recommence. La liste F contient à la fin tous les facteurs.

On utilise en plus une astuce pour gagner du temps: on commence par trouver tous les facteurs “2” (s'il y en a), ce qui permet après de n'essayer que les nombres impairs. Pour des valeurs de n importantes, on divise ainsi les essais par 2.

Les tentatives de division s'arrêtent à racine de n, parce que si on n'a pas trouvé de facteur avant, on n'en trouvera plus, et donc le n en question est premier (et on a donc fini la décomposition). Pour calculer la racine carrée de n, on utilise la fonction lsqrt() définie ici: http://python.jpvweb.com/mesrecettespython/racine_entiere. On aurait pu faire un test avec i*i>n, mais cela conduirait à faire la multiplication i*i pour chaque valeur de i, alors que la racine de n ne change que lorsque n change.

Voici le code:

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def facteurs(n):
    """facteurs(n): décomposition d'un nombre entier n en facteurs premiers"""
    F = []
    if n==1:
        return F
    # recherche de tous les facteurs 2 s'il y en a
    while n>=2:
        x,r = divmod(n,2)
        if r!=0:
            break
        F.append(2)
        n = x
    # recherche des facteurs 1er >2
    i=3
    rn = lsqrt(n)+1
    while i<=n:
        if i>rn:
            F.append(n)
            break
        x,r = divmod(n,i)
        if r==0:
            F.append(i)
            n=x
            rn = lsqrt(n)+1
        else:
            i += 2
    return F
 
# exemple d'utilisation:
print facteurs(100)  # affiche [2,2,5,5]
print facteurs(123456789)  # affiche [3,3,3607,3803]
print facteurs(12345678901234567890) # affiche [2,3,3,5,101,3541,3607,3803,27961L]
 
# et test avec un nombre premier
print facteurs(4291979)  # affiche [4291979]

Bien que passant par un calcul systématique “bête”, cette fonction est rapide. Par exemple:

print facteurs(12345678901234567890)
[2, 3, 3, 5, 101, 3541, 3607, 3803, 27961]

Résultat trouvé en moins d'un 1/10 de seconde (essayez donc de faire ça à la main…).

La rapidité du calcul dépend de la quantité des facteurs et de leur taille. Le temps le plus long étant obtenu, pour une taille donnée, avec un nombre premier, ou avec un nombre composé de 2 nombres premiers grands. Par exemple:

print facteurs(6082717798076598743L)
[1536921011, 3957729613L]
 
print facteurs(4403961009416440783L)
[1417259917, 3107377099L]
 
print facteurs(1068903645797520007L)
[589884577, 1812055591L]
 
print facteurs(1036362964755146009L)
[373148107, 2777350187L]
 
print facteurs(433427761334691989L)
[220147591, 1968805379L]
 
print facteurs(2809239098183306821L)
[725122477, 3874158073L]

Ce qui prend environ de 7 à 15 mn de calcul.

Par contre, pour traiter des nombres de plusieurs centaines de chiffres comme on en trouve en cryptographie, il faudra nécessairement développer d'autres méthodes…

On obtient donc le résultat sous forme de liste, mais vous souhaitez peut-être la transformer en expression avec tous les facteurs prêts à être re-multipliés. Alors, vous pouvez créer la fonction suivante:

def mulfacteurs(L):
    """ mulfacteurs(L): présente la liste des facteurs en facteurs multipliés"""
    if L==[]:
        ch = ""
    else:
        ch = "%s" % L[0]
        for k in xrange(1,len(L)):
            ch = ch + "*" + "%s" % L[k]
    return ch

Dans ce cas, la liste précédente est transformée en: “2*3*3*5*101*3541*3607*3803*27961”

Comme c'est une expression sous forme de chaine vous pouvez en demander le calcul par eval():

eval(“2*3*3*5*101*3541*3607*3803*27961”) qui redonne bien (heureusement! ) le nombre initial donné: 12345678901234567890.

Vous pouvez tester la fonction facteurs(n) avec la Calculext ici: http://calculext.jpvweb.com, mais soyez raisonnable: avec un nombre trop grand, vous risquez de dépasser le temps maxi de calcul autorisé sur le serveur.

Amusez-vous bien!