[PDF] Corrigé : ave Cesar (X2008 - MP) Partie I. Codage de César

View - Download Corrigé : ave Cesar (X2008 - MP) Partie I. Codage de César

Previous PDF

Next PDF

informatique commune Corrigé : ave Cesar (X2008 - MP)Partie I.C odagede C ésar

Question 1.

Le codage de"maitrecorbeau"avec un décalage de 5 donne :"hvdomzxjmwzvp".

Question 2.defcodageCesar(t, d):

tprime = [] forxint: tprime.append((xd) % 26) returntprimeQuestion 3.Il suffit de remplacerdpard:defdecodageCesar(t, d): tprime = [] forxint: tprime.append((x + d) % 26) returntprimeQuestion 4. deffrequences(tprime): occ = [0]*26 forxintprime: occ[x] += 1

returnoccQuestion 5.On commence par écrire une fonction qui, à partir du tableau des fréquences, calcule la clef sachant que la

valeur maximale de ce tableau correspond à la lettre"e"représentée par l"entier 4 :defclef(occ):

imax = 0 foriinrange (1, 26): ifocc[i] > occ[imax]: imax = i return(4imax) % 26La fonction de décodage automatique s"écrit alors : defdecodageAuto(tprime): d = clef(frequences(tprime)) returndecodageCesar(tprime, d)page 1

Partie II.C odagede V igenère

Question 6.Avec la clef"jean", le texte"becunfromage"est codé par :"kichwjrbvegr".

Question 7.Cette fois, le décalage se fait vers la droite d"une valeur égale àc[i % k], oùidésigne l"indice de la lettre à

coder etkla longueur de la clefc.defcodageVigenere(t, c): k =len(c) tprime = [] for(i, x)inenumerate (t): tprime.append((x + c[i % k]) % 26) returntprimeQuestion 8.On utilise les formules suivantes, valables pour (x;y)2N2nf(0;0)g: pgcd(x;0) =x;pgcd(0;y) =y;pgcd(x;y) =8 >><>>:pgcd(x;yx) six6y pgcd(xy;y) sinondefpgcd(a, b): x, y = a, b whilex > 0andy > 0: ifx <= y: y= x else: x= y ifx == 0 : returny else:

returnxQuestion 9.Pour calculer ce pgcd, on utilise les formules : pgcd(0;b) =bet pgcd(a;b;c) = pgcd(pgcd(a;b);c).defpgcdDesDistancesEntreRepetitions(tprime, i):

d = 0 forjinrange (i+3,len(tprime)2): iftprime[i:i+3] == tprime[j:j+3]: d = pgcd(d, ji) returndQuestion 10.

Il faut maintenant appliquer la fonction précédente pour tout06i < n5et calculer le pgcd de toutes les

valeurs obtenues pour espérer obtenir la longueur de la clef :deflongueurDeLaClef(tprime): d = 0 foriinrange (len(tprime)5): d = pgcd(d, pgcdDesDistancesEntreRepetitions(tprime, i)) returndQuestion 11. La fonctionpgcdDesDistancesEntreRepetitionsappelle la fonctionpgcdau plus une fois pour chacune

des valeursj2~i+3;n2~, soit au plus(ni5)fois. La fonctionlongueurDeLaCleffait donc appel à la fonctionpgcd

un nombre de fois au plus égal à : n6X i=0(ni4) =(n4)(n3)2 1n22 La fonctionlongueurDeLaClefest de complexité quadratique. page 2

Question 12.Une fois la longueurkde la clef connue, on sait que toutes les lettres séparées par une distance égale à

un multiple deksont codées par le même décalage. On peut donc appliquer la méthode de calcul des fréquences pour

déterminer ce décalage, et donc chacune des lettres de la clef.

Concrètement, pour touti2~0;k1, les lettres du sous-tableaut[i::k]ont toutes été codées avec le même décalagedi.

On peut donc utiliser la fonctiondecodageAutoécrite à la question 5 pour décoder cette partie du message.defdecodageVigenereAuto(tprime):

n =len(tprime) k = longueurDeLaClef(tprime) t = [None]*n foriinrange (k): t[i::k] = decodageAuto(tprime[i::k]) returntpage 3quotesdbs_dbs28.pdfusesText_34

[PDF] Correction CNC, partie informatique

[PDF] CONCOURS DE L 'INTERNAT EN PHARMACIE - CNCI

[PDF] Le Directeur Gnral

[PDF] Loi 09-08 - CNDP

[PDF] Conduite en douane des colis postaux L acheminement d

[PDF] Untitled - CNDP

[PDF] CNEC CNEC - Institut National Du Cancer

[PDF] français - Cned

[PDF] au service de toutes les reussites 2017 - Cned

[PDF] Calendrier_Etablissements ? l 'Etranger_2016-2017

[PDF] Livret de l étudiant du DECESF - Cned

[PDF] Calendrier des envois de devoirs

[PDF] master 2 sciences de l 'éducation ? distance international

[PDF] CNED : DAEU A - Université de Paris-Sud, Paris-11

[PDF] Direction - Cned