tps/testProbabilite.py

   1 from random import *
   2
   3
   4
   5
   6
   7 def testPrimaliteFermat(n,t):
   8     testes = []
   9     j = 0
  10     ret = True
  11     while j < t and ret :
  12         # choix de a
  13         a = randint(1,n-1)
  14         while a in testes:
  15             a = randint(1,n-1)
  16         #calcul de a^(n-1) [n]
  17         #if a**(n-1) % n != 1 :
  18         if pow(a,n-1,n) != 1 :
  19             ret = False
  20         else :
  21             j+= 1
  22             testes +=[a]
  23     return ret
  24
  25
  26
  27
  28
  29
  30
  31 def testPrimaliteMillerRabin(n,t):
  32     testes = []
  33     if n % 2 == 0:
  34         return False
  35
  36     # ecrire  n-1 comme 2**s * d
  37     s,d = 0, n-1
  38     while d % 2 == 0 :
  39         s +=1
  40         d /= 2
  41     j = 0
  42     ret = True
  43     while j < t and ret :
  44         # choix de a
  45         a = randint(1,n-1)
  46         while a in testes:
  47             a = randint(1,n-1)
  48         # calcul de a^(d) [n]
  49         if pow(a, d, n) != 1:
  50             ret = False
  51             r=0
  52             while r < s and not ret:
  53                 if pow(a, 2**r * d, n) ==  n-1:
  54                     ret= True
  55                 else :
  56                     r+=1
  57         j+=1
  58         #print j
  59         testes +=[a]
  60     return ret
  61
  62
  63 n=561
  64 print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,500)
  65 print "probabilite d'etre premier (Miller Rabin)", testPrimaliteMillerRabin(n,3)
  66
  67 n= 39341
  68 print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,500)
  69 print "probabilite d'etre premier (Miller Rabin)", testPrimaliteMillerRabin(n,30)
  70
  71 n=651693055693681
  72 print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,500)
  73 print "probabilite d'etre premier (Miller Rabin)", testPrimaliteMillerRabin(n,30)
  74