tps/testProbabilite.py~

   1 from random import *
   2
   3
   4
   5 testes = []
   6
   7 def testPrimaliteFermat(n,t):
   8     global testes
   9     j = 0
  10     ret = True
  11     while j < t and ret :
  12         print j
  13         # choix de a
  14         a = randint(1,n-1)
  15         while a in testes:
  16             a = randint(1,n-1)
  17         #calcul de a^(n-1) [n]
  18         #if a**(n-1) % n != 1 :
  19         if pow(a,n-1,n) != 1 :
  20             ret = False
  21         else :
  22             j+= 1
  23             testes +=[a]
  24     return ret
  25
  26
  27
  28
  29
  30
  31
  32 def testPrimaliteMillerRabin(n,t):
  33     global testes
  34     if n % 2 == 0:
  35         return False
  36
  37     # ecrire  n-1 comme 2**s * d
  38     s,d = 0, n-1
  39     while d % 2 == 0 :
  40         s +=1
  41         d /= 2
  42     #testes = []
  43     j = 0
  44     ret = True
  45     while j < t and ret :
  46         # choix de a
  47         a = randint(1,n-1)
  48         while a in testes:
  49             a = randint(1,n-1)
  50         # calcul de a^(d) [n]
  51         if pow(a, d, n) != 1:
  52             ret = False
  53             r=0
  54             while r < s and not ret:
  55                 if pow(a, 2**r * d, n) ==  n-1:
  56                     ret= True
  57                 else :
  58                     r+=1
  59         j+=1
  60         #print j
  61         testes +=[a]
  62
  63     return ret
  64
  65
  66 n=651693055693681
  67 #n= 39341
  68 #n=561
  69
  70 #print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,500)
  71 #print "probabilite d'etre premier (Miller Rabin)", testPrimaliteMillerRabin(n,30)
  72
  73
  74 def genereUnNombrePremier(nbChiffre):
  75     estPremier=False
  76     compteur, r = 0, 0
  77     mini = 10**(nbChiffre-2)
  78     maxi = 10**(nbChiffre-1)-1
  79     chiffreFinal=[1,3,7,9]
  80     while (not estPremier):
  81         r = randint(mini,maxi)*10
  82         r += chiffreFinal[randint(0,3)]
  83         #print r
  84         compteur += 1
  85         if testPrimaliteMillerRabin(r,50):
  86             estPremier = True
  87     return (r,compteur)
  88
  89 nbit,l=0,100
  90 for k in range(l):
  91     (r,n)= genereUnNombrePremier(100)
  92     nbit += n
  93     print r
  94 print float(nbit)/l
  95
  96 """
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113 t = 50
 114 n = 393413 #premier
 115 n=651693055693681
 116 #n = 393417 #premier
 117 n=9623827 #et  343570291. % res=2953*3259     res = 17729*19379
 118 print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,t)
 119 print "probabilite d'etre premier (MILLER-RABIN)", testPrimaliteMillerRabin(n,t)
 120
 121
 122
 123
 124 """
 125