GroupeISN: attachment:x2008.py de Projets

   1 # Conversion d'une chaîne en un tableau d'entiers
   2 # Les 26 lettres (majuscules) sont codées par les nombres de 0 à 25
   3 def conversion_chaine_tab (ch):
   4     n=len(ch)
   5     result=[0]*n
   6     for i in xrange(n):
   7         result[i]=ord(ch[i])-65
   8     return result
   9 
  10 # Fonction inverse de la précédente
  11 def conversion_tab_chaine(t):
  12     result=""
  13     n=len(t)
  14     for i in xrange(n):
  15         result=result + chr(t[i]+65)
  16     return result
  17 
  18 #                               PARTIE I
  19 
  20 # Question 1
  21 def codageCesar(t,n,d):
  22     result=[0]*n
  23     for i in xrange(n):
  24         result[i]=(t[i]-d)%26
  25     return result
  26 
  27 #Question 2
  28 def decodageCesar(t,n,d):
  29     result=[0]*n
  30     for i in xrange(n):
  31         result[i]=(t[i]+d)%26
  32     return result
  33 
  34 #Question 4
  35 def frequence(t):
  36     n=len(t)
  37     result=[0]*26
  38     for i in xrange(n):
  39         result[t[i]]=result[t[i]]+1
  40     return result
  41 
  42 # Fonction qui calcule le décalage, utilisée par la fonction decalageAuto
  43 def calcule_decalage(t):
  44     indmax=0
  45     for i in xrange(26):
  46        if t[i]>t[indmax]:
  47            indmax=i
  48     return (4-indmax)%26
  49 
  50 # Question 5
  51 def decodageAuto(t):
  52     n=len(t)
  53     f=frequence(t)
  54     d=calcule_decalage(f)
  55     result=decodageCesar(t,n,d)
  56     return result
  57 
  58 #                                PARTIE II
  59 
  60 # Question 7
  61 def codageVigenere(t,n,c,k):
  62     result=[0]*n
  63     j=0
  64     for i in xrange(n):
  65         d=-c[j]%26
  66         result[i]=(t[i]-d)%26
  67         j=(j+1)%k
  68     return result
  69 
  70 # Cette fonction permet le décodage lorsque le clé est connue
  71 def decodageVigenere(t,n,c,k):
  72     result=[0]*n
  73     j=0
  74     for i in xrange(n):
  75         d=-c[j]%26
  76         result[i]=(t[i]+d)%26
  77         j=(j+1)%k
  78     return result
  79 
  80 # Question 8
  81 def pgcd(x,y):
  82     a=x
  83     b=y
  84     while b!=0:
  85         while a>=b:
  86             a=a-b
  87         c=a
  88         a=b
  89         b=c
  90     return a
  91 
  92 # Question 9
  93 def pgcdDesDistancesEntreRepetitions(t,n,i):
  94     result=0
  95     for j in xrange(i+3,n-2):
  96         if t[i]==t[j] and t[i+1]==t[j+1] and t[i+2]==t[j+2]:
  97             result=pgcd(result,j-i)
  98     return result
  99 
 100 # Question 10
 101 def longueurDeLaCle(t,n):
 102     result=0
 103     for i in xrange(n-2):
 104         result=pgcd(result,pgcdDesDistancesEntreRepetitions(t,n,i))
 105     return result
 106 
 107 # Question 11 et 12
 108 def decodageVigenereAuto(t,n):
 109     lg=longueurDeLaCle(t,n)
 110     cle=[0]*lg
 111     for i in xrange(lg):
 112         f=[0]*26
 113         for k in xrange(i,n,lg):
 114             f[t[k]]=f[t[k]]+1
 115         indmax=0
 116         for k in xrange(26):
 117             if f[indmax]<f[k]:
 118                 indmax=k
 119         cle[i]=(indmax-4)%26
 120     return decodageVigenere(t,n,cle,lg)
 121     
 122 # Pour tester le codage de César lorsque le décalage est connu (j'ai fait en sorte que E soit la lettre la plus fréquente)
 123 def test0():
 124     x=conversion_chaine_tab("MESTRECORBEAU")
 125     d=5
 126     y=codageCesar(x,len(x),d)
 127     z=decodageCesar(y,len(y),d)
 128     print conversion_tab_chaine(z)
 129 
 130 #Pour tester le codage de César avec un décodage qui calcule le décalage
 131 def test1():
 132     x=conversion_chaine_tab("MESTRECORBEAU")
 133     d=5
 134     y=codageCesar(x,len(x),d)
 135     z=decodageAuto(y)
 136     print conversion_tab_chaine(z)
 137 
 138 # Pour tester le codage et décodage de Vigenere connaissant le texte de la clé
 139 def test2():
 140     t=conversion_chaine_tab("ECOLEPOLYTECHNIQUE")
 141     n=len(t)
 142     c=conversion_chaine_tab("CONCOURS")
 143     k=len(c)
 144     x=codageVigenere(t,n,c,k)
 145     print conversion_tab_chaine(x)
 146     y=decodageVigenere(x,n,c,k)
 147     print conversion_tab_chaine(y)
 148 
 149 # Pour tester Vigenere en calculant le texte de la clé qui a été utilisé pour le codage
 150 def test3():
 151     txt="""SOUVENTPOURSAMUSERLESHOMMESDEQUIPAGEPRENNENTDESALBATROSVASTESOISEAUXDESMERSQUISUIVENTINDOLENTSCOMPAGNONSDEVOYAGELENAVIREGLISSANTSURLESGOUFFRESAMERSAPEINELESONTILSDEPOSESSURLESPLANCHESQUECESROISDELAZURMALADROITSETHONTEUXLAISSENTPITEUSEMENTLEURSGRANDESAILESBLANCHESCOMMEDESAVIRONSTRAINERACOTEDEUXCEVOYAGEURAILECOMMEILESTGAUCHEETVEULELUINAGUERESIBEAUQUILESTCOMIQUEETLAIDLUNAGACESONBECAVECUNBRULEGUEULELAUTREMIMEENBOITANTLINFIRMEQUIVOLAITLEPOETEESTSEMBLABLEAUPRINCEDESNUEESQUIHANTELATEMPETEETSERITDELARCHERBAUDELAIRE"""
 152     print txt
 153     t=conversion_chaine_tab(txt)
 154     n=len(t)
 155     c=conversion_chaine_tab("SCUBA")
 156     k=len(c)
 157     x=codageVigenere(t,n,c,k)
 158     print
 159     print "TEXTE codé"
 160     print conversion_tab_chaine(x)
 161     print
 162     print "TEXTE décodé"
 163     y=decodageVigenereAuto(x,n)
 164     print conversion_tab_chaine(y)
 165 
 166 
 167