tps/testProbabiliteAvecGeneration.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 """
  90 nbit,l=0,100
  91 for k in range(l):
  92     (r,n)= genereUnNombrePremier(100)
  93     nbit += n
  94     print r
  95 print float(nbit)/l
  96
  97 """
  98
  99 def bezout(a,b):
 100   if b==0: return [1,0]
 101   else:
 102     uv= bezout(b,a%b)
 103     return [uv[1],uv[0]-uv[1]*(a/b)]
 104
 105
 106
 107 (p,_)= genereUnNombrePremier(100)
 108 (q,_)= genereUnNombrePremier(100)
 109
 110 n=p*q
 111 phi=(p-1)*(q-1)
 112
 113 (e,_)= genereUnNombrePremier(30)
 114 print "cle publique",e
 115
 116 (d,_)=bezout(e,phi)
 117 d = d%phi
 118 print "cle privee",d
 119
 120
 121 m=3402752281514000316845
 122
 123 a = pow(m,e,n)
 124 print "message encodee ",a
 125
 126 mp = pow(a,d,n)
 127 print "message decodee ",mp
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139 """
 140
 141
 142 t = 50
 143 n = 393413 #premier
 144 n=651693055693681
 145 #n = 393417 #premier
 146 n=9623827 #et  343570291. % res=2953*3259     res = 17729*19379
 147 print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,t)
 148 print "probabilite d'etre premier (MILLER-RABIN)", testPrimaliteMillerRabin(n,t)
 149
 150
 151
 152
 153 """
 154