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:
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:
# ============================================================================= 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:
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:
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!