Un nombre premier est un nombre entier qui ne peut être divisé que par lui-même et par 1. Par exemple: 2, 3, 5, 7, …

Au contraire, le nombre 6, par exemple, n'est pas premier, car il est divisible par 2 et par 3.

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

Si vous cherchez des exemples de nombres premiers, il y en a pas mal ici: http://nombrespremiersliste.free.fr/. Et il y en a une infinité…

On va chercher ici comment on peut savoir qu'un nombre donné est premier ou pas.

Ce n'est pas qu'une question théorique: Cela fait partie, par exemple, des méthodes de cryptographie.

Le calcul est simple dans son principe: on essaye de diviser le nombre donné par des nombres successifs à partir de 2, et si on trouve un diviseur, le nombre donné n'est pas premier.

On s'arrête à racine de n, parce que si on n'a pas trouvé de diviseur avant, on n'en trouvera plus: le nombre est alors premier.

La fonction renvoie “True” si le nombre donné est premier, et “False” dans le cas contraire.

Petit complément ici, on a une fonction “racine carrée de …”. Mais cette racine carrée nécessiterait normalement l'utilisation de la fonction sqrt() du module math, qui entrainerait une conversion du nombre en flottant, alors qu'on est ici avec des entiers, et éventuellement des entiers très long. Alors, nous utilisons une fonction “lsqrt(n)” qui calcule la racine carrée entière de n'importe quel nombre entier, y compris très long (10000 chiffres si vous voulez) sans nécessiter de conversion avec des flottants: cette fonction est décrite sur ce présent site ici: http://python.jpvweb.com/mesrecettespython/racine_entiere.

def estpremier(n):
    """estpremier(n): dit si un nombre est premier (renvoie True ou False)"""
    if n<7:
        if n in (2,3,5):
            return True
        else:
            return False
    # si n est pair et >2 (=2: cas traité ci-dessus), il ne peut pas être premier
    if n & 1 == 0:
        return False
    # autres cas
    k=3
    r=lsqrt(n)
    while k<=r:
        if n % k == 0:
            return False
        k+=2
    return True
 
 
# =============================================================================
# Exemple d'utilisation:
print estpremier(10)  # affiche False
print estpremier(11)  # affiche True
print estpremier(999999937)  # affiche True

Cas particulier: même si ça a un petit côté artificiel, la définition dit que le nombre 1 n'est pas premier: la fonction estpremier(1) renvoie donc False.

Vous pouvez tester cette fonction avec la Calculext ici: http://calculext.jpvweb.com

Cette fonction est très rapide. Mais dans certaines applications, par exemple la cryptographie, son utilisation avec des nombres de plusieurs centaines de chiffres conduit à des temps inacceptables.

Pour ces applications, il faudra recourir à des tests dits “probabilistes”: c'est l'objet du chapitre suivant.

Source d'inspiration:

• http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

• http://en.literateprograms.org/Miller-Rabin_primality_test_(Python)

L'originalité de ce test est que le résultat obtenu n'est pas certain… mais il peut devenir aussi probable qu'on le veut en recommençant plusieurs fois!

En contrepartie, il est beaucoup plus rapide pour les entiers très longs comme on en trouve en cryptographie.

Voilà le code. Il est auto-documenté, et vous trouverez aux adresses mentionnées ci-dessus les explications techniques nécessaires.

Pour accélérer l'exécution:

• j'ai ajouté la liste des nombres premiers jusqu'à 1024: on peut au moins se débarrasser rapidement du problème si n<=1024.

• j'ai ajouté une fonction qui fait l'exponentiation modulaire: (a**b)%n. On n'aurait pas dû en avoir besoin avec Python, parce que la fonction intégrée pow(a,b,n) fait la même chose dès qu'on ajoute le 3ème argument “n”. Mais cette fonction ne marchait pas chez moi.

# =============================================================================
petitspremiers = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,
    79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,
    179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,
    269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,
    367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,
    461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,
    571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,
    661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,
    773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,
    883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,
    1009,1013,1019,1021]
 
# =============================================================================
def lpowmod(a, b, n):
    """exponentiation modulaire: calcule (a**b)%n"""
    r = 1
    while b>0:
        if b&1==0:
            b = b>>1
        else:
            r = (r*a)%n
            b = (b-1)>>1
        a = (a*a)%n
    return r
 
# =============================================================================
#  Test de primalité probabiliste de Miller-Rabin
def _millerRabin(a, n):
    """Ne pas appeler directement (fonction utilitaire). Appeler millerRabin(n, k=20)"""
    # trouver s et d pour transformer n-1 en (2**s)*d
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
 
    # calculer l'exponentiation modulaire (a**d)%n
    apow = lpowmod(a,d,n) # =(a**d)%n
 
    # si (a**d) % n ==1 => n est probablement 1er
    if apow == 1:
        return True
 
    for r in xrange(0,s):
        # si a**(d*(2**r)) % n == (n-1) => n est probablement 1er
        if lpowmod(a,d,n) == n-1:
            return True
        d *= 2
 
    return False
 
# ========================
def millerRabin(n, k=20):
    """Test de primalité probabiliste de Miller-Rabin"""
    global petitspremiers
 
    # éliminer le cas des petits nombres <=1024
    if n<=1024:
        if n in petitspremiers:
            return True
        else:
            return False
 
    # éliminer le cas des nombres pairs qui ne peuvent pas être 1ers!
    if n & 1 == 0:
        return False
 
    # recommencer le test k fois: seul les nb ayant réussi k fois seront True
    for repete in xrange(0, k):
        # trouver un nombre au hasard entre 1 et n-1 (bornes inclues)
        a = random.randint(1, n-1)
        # si le test echoue une seule fois => n est composé
        if not _millerRabin(a, n):
            return False
    # n a réussi les k tests => il est probablement 1er
    return True

Vous voyez que la fonction “millerRabin(n, k=20)” a un 2ème argument “k=20”. En fait, il s'agit de recommencer k fois le même test pour être plus sûr du résultat: seuls les nombres ayant été trouvés “premiers” k fois de suite seront déclarés “premier” (pardon “probablement premier”).

Alors, commençons avec k=1.

J'ai fait des tests systématiques avec le code suivant:

nb = 0 # compteur du nombre total de boucle
np = 0 # compteur de nombre premiers
e1 = 0 # compteur de faux négatifs
e2 = 0 # compteur de faux positifs
while nb<1000000:
    n =random.randint(1000000,9999999)
    nb += 1
    res = millerRabin(n, 1)
    res2 = estpremier(n)
 
    if res2: # le nombre est effectivement premier
        np += 1
        if res!=res2:
            # faux négatif: dit que n n'est pas premier alors qu'il l'est
            e1 += 1
    else:  # le nombre n'est effectivement pas premier
        if res!=res2:
            # faux positif: dit que n est premier alors qu'il ne l'est pas
            e2 += 1
 
print nb, np, e1, e2

Avec ce code, je fais 1000000 (un million) de tirages au hasard de nombres entiers à 7 chiffres (entre 1000000 et 9999999). Je les teste avec les divisions (test juste à 100%), et je trouve environ 65000 nombres premiers.

Je constate alors:

• avec k=1 (=un seul test de Miller-Rabin): j'ai environ 15 “faux positif” (=nombre déclaré 1er alors qu'il ne l'est pas), ce qui donne un % d'erreur déjà très faible (0.02%), et aucun “faux négatif”.

• avec k=20 (=20 fois le même test sur le même nombre): je n'ai plus aucun faux positif.

Et, bien sûr, on peut augmenter k pour être encore plus sûr (k=100, k=1000, …) avec la sanction inévitable sur la durée d'exécution.

En conclusion: ce test probabiliste est réellement utilisable!

A priori, on n'accepte le test probabiliste que parce qu'il apporte un gain sur la durée de traitement. Mais est-qu'on a effectivement un gain?

Voilà mon code de vérification:

t1 = 0
t2 = 0
nb = 10000
for i in xrange(0,nb):
 
    n =random.randint(10000000000,99999999999)
 
    tps = time.clock()
    r = millerRabin(n)
    t1 += time.clock()-tps
 
    tps = time.clock()
    r = estpremier(n)
    t2 += time.clock()-tps
 
print t1/nb, t2/nb, t2/t1

Résultat: avec des nombres au hasard de 7 chiffres, le test probabiliste de Miller-Rabin est 5 fois plus lent que le test avec divisions!

Augmentons alors la taille des nombres à tester:

• nombres de 8 chiffres: le test probabiliste est encore environ 2 fois plus lent

• nombre de 9 chiffres: durée de traitement pratiquement égale

• nombre de 10 chiffres: le test probabiliste prend 6 fois moins de temps

• nombre de 11 chiffres: le test probabiliste prend 19 fois moins de temps

• etc…

La conclusion est que: en dessous de 100000000 (100 millions), il faut préférer le test par division, mais au dessus, on utilise forcément le test probabiliste.

Allons plus loin.

On fabrique un code qui va générer des nombres premiers de grande taille:

def genpremier(nbits):
    while True:
        n = random.randint(2, 2**nbits)
        if millerRabin(n):
            return n

Et on va essayer de faire passer le test sur ces nombres ainsi générés avec le code suivant:

nbits = 512
n = genpremier(nbits)
print n
print len(str(n))
tps = time.clock()
r = millerRabin(n)
print r, time.clock()-tps

Essayons:

Avec nbits=512, on peut fabriquer un nombre premier composé de 154 chiffres comme celui-ci (en une seule ligne!):

35613903710514819437378342743622758338347006734129794271845999749351085143332639
83788419458833937814570157135046780537933798266359120238502354979408286041

Le test probabiliste de Miller-Rabin s'exécutera en 0.6 seconde environ.

Avec nbits=1024, on peut fabriquer un nombre premier composé de 308 chiffres comme celui-ci (en une seule ligne!):

86987419046168366755572717322566259821329931297187288277478284567620228620225262
24867339857915141787745032523090399066662262093364931916786560056631348505535372
27567168244652135224002440830715202673132870333379687459126628923351165611017098
36477229998761104239796364898779650068315812315509700982569516198289

Le test probabiliste de Miller-Rabin s'exécutera en 6 secondes environ.

Avec nbits=2048, on peut fabriquer un nombre premier composé de 617 chiffres comme celui-ci (en une seule ligne!):

30097271632819368575013534852020269977363380847447333337874958693250073145347975
11265446881420188730559710583494357478847485341669351262994204056603743911763409
41893718846998447360664780972998861942419868502946280866629626938733063121162492
38054627855410942579429289849405384090782470871872417703469727253645261267291732
80230017562683088365977705916580439846554380323402487626188606631481605891184749
64512332470213120723911392392888705895724840269605784349569201885188201952160258
20122801095151820333658973516999533252007897451445314260928371262801266255489905
101824143935643231671444171618932687912539391349548271371

Le test probabiliste de Miller-Rabin s'exécutera en 15 secondes environ.

Je n'ose pas imaginer le nombre de mois qu'il faudrait pour tester ce nombre avec la méthode des divisions!

Amusez-vous bien!