[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_dbs46.pdfusesText_46

[PDF] le chiffre des unité de 13 puissance 2011

[PDF] le chinois pour les nuls pdf gratuit

[PDF] Le chlore

[PDF] le chloroforme utilisée comme anesthésie

[PDF] LE CHOC DES IMAGES

[PDF] le choc du chagrin et la pitié analyse

[PDF] Le Chocolat , Boisson a la mode au XVIII e siècle !

[PDF] le chocolat cp ce1

[PDF] le choix d'une solution technique

[PDF] le choix d'une femme libre

[PDF] le choix de l'amour final en francais

[PDF] le choix de l'amour streaming vf

[PDF] Le choix de la combinaison productive

[PDF] le choix de la propriete

[PDF] le choix des modes de financement