(*############ EXERCICE 1 ############*) (* Question 1 *) let suite u0 n = let rec aux res = function |0 -> res |m -> aux (16033*res mod 65519) (m-1) in aux u0 n;; (* u_787 = 56976 et u_997392 = 60751*) (* Question 2 *) let int_of_bool b = if b then 1 else 0;; let indices u0 i0 i1 = let u1 = suite2 u0 1 in let u2 = suite2 u1 1 in let rec compte ug u ud accu = function |0 -> accu |m -> let b = (i1-m+1 >= i0) & ((u mod 11)*(1+(ud mod 11))>= (ug mod 11)) in compte u ud (16033*ud mod 65519) (accu+(int_of_bool b)) (m-1) in compte u0 u1 u2 0 i1;; (* i0 indice de début, i1 indice de fin compte res_u accu m: u = valeur de u_[i1-m] ud = valeur de u_[i1-m+1] ug = valeur de u_[i1-m-1] accu = card des indices i<=i1-m tq inégalité vérifiée *) (* indices 2 1000 9999 = 7640 indices 2 1000 999999 = 846366 *) (*############ EXERCICE 4 ############*) (* Question 1 *) let int_of_lettre a = match a with | `a`..`z` -> (int_of_char a)-97 | `A`..`Z` -> (int_of_char a)-65 | _ -> -1;; let compteLettres fichier = let freq = make_vect 26 0 in let canal = open_in fichier in try let rec aux () = let i = int_of_lettre (input_char canal) in match i with | -1 -> aux () | _ -> freq.(i) <- freq.(i)+1 ; aux () in aux () with End_of_file -> (); freq;; let frequenciser freq = let somme = it_list (prefix +) 0 (list_of_vect freq) in map_vect (fun x -> (float_of_int x)/.(float_of_int somme)) freq ;; let frequence fichier = frequenciser (compteLettres fichier);; (* Question 2 *) let ic freq = it_list (prefix +.) 0. (list_of_vect (map_vect (function x -> x*.x) freq));; (* pour un texte français, ic = 0.074; pour un texte aléatoire, ic = 0.038 *) (* création d'un message aléatoire *) #open "random";; let make_texte_aleatoire nom taille = let canal = open_out nom in for i=1 to taille do output_char canal (char_of_int ((int 25)+97)); if (i mod 30) = 0 then output_char canal `\n` done; close_out canal;; (* Question 3 *) #open "printf";; let afficheFreq freq nom = let canal = open_out nom in for i = 0 to 25 do let s = sprintf "%c %.4f\n" (char_of_int (i+97)) freq.(i) in output_string canal s done; close_out canal;; (* Question 4 *) (* vect_of_cle transforme un mot en un tableau comportant le code des lettres modulo 26 de ce mot *) let vect_of_cle cle = let n = string_length cle in let f = function k -> (int_of_char (cle.[k]))-97 in init_vect n f;; let chiffreVigenereBis cle nom = let n = vect_length cle in let texte = open_in nom in let codage = open_out ("codage_"^nom) in let pos = ref 0 in let compteur = ref 0 in try let rec aux () = let i = int_of_lettre (input_char texte) in match i with | -1 -> aux () | _ -> let new = ((cle.(!pos)+i) mod 26)+97 in output_char codage (char_of_int new); pos := (!pos + 1) mod n; compteur := (!compteur + 1) mod 50; if !compteur = 0 then output_char codage `\n`; aux () in aux () with End_of_file -> (); close_in texte; flush codage; close_out codage;; (* pos représente l'indice courant de la lettre de la clé qui permettra le chiffrement, on ne l'incrémente uniquement lorsqu'on rencontre un caractère chiffrable; compteur compte le nombre de lettres qu'on a chiffrées modulo 50, permet d'introduire des retours à la ligne réguliers dans le chiffré *) let chiffreVigenere cle nom = chiffreVigenereBis (vect_of_cle cle) nom;; let dechiffreVigenere cle nom = let cle2 = vect_of_cle cle in let cle3 = map_vect (function i -> 26-i) cle2 in chiffreVigenereBis cle3 nom;; (* pour déchiffrer, on chiffre avec la clé opposée (0 <-> 25) de celle utilisée pour le chiffrement *) (* Question 5 *) let icSousTexte nom n = let texte = open_in nom in let matrice = make_matrix n 26 0 in let pos = ref 0 in try let rec aux () = let i = int_of_lettre (input_char texte) in match i with | -1 -> aux () | _ -> matrice.(!pos).(i) <- matrice.(!pos).(i) + 1; pos := (!pos + 1) mod n; aux () in aux () with End_of_file -> (); close_in texte; let matrice2 = map_vect frequenciser matrice in let matrice3 = map_vect ic matrice2 in let a = map_vect (function x -> printf "%.4f\n" x) matrice3 in matrice;; (* matrice.(j) est le tableau du nombre de lettres dans le sous texte t(j) *) (* Question 6 *) let rechercheMax tab = let res = ref min_int in let f x = res:= max x (!res) in do_vect f tab; !res;; let rechercheCleFr matrice = let n = vect_length matrice in let cle = create_string n in for j=0 to (n-1) do let max = rechercheMax matrice.(j) in let lettre = char_of_int (((max+22) mod 26)+97) in cle.[j] <- lettre done; cle;; (* on exécute le programme icSousTexte pour différentes longueurs de clé, dès que tous les indices de coïncidence sont proches de 0.074, la longueur de clé a été trouvée, et on utilise la matrice retournée pour retrouver la clé secrète à l'aide de rechercheCleFr: dans chaque sous-mot, la lettre apparaissant le plus souvent correspond à la lettre E *) (*############ EXERCICE 5 ############*) #open "graphics";; #open "printf";; open_graph "";; let xmax = size_x () and ymax = size_y ();; let ox = xmax/2 and oy = ymax/2;; let pi = 2.*.asin (1.);; let sommetsPolygone n scale angle= let nn = float_of_int n in let rec listeSommets = function | -1 -> [] | k -> let kk = float_of_int k in let xk = int_of_float (scale*.cos(2.*.kk*.pi/.nn+.angle)) and yk = int_of_float (scale*.sin(2.*.kk*.pi/.nn+.angle)) in (xk+ox,yk+oy)::(listeSommets (k-1)) in listeSommets n;; let rec plotListe = function | [] -> () | (a,b)::q -> lineto a b; plotListe q;; let plotPolygone n scale angle = let listeS = sommetsPolygone n scale angle in let (a,b) = hd(listeS) in moveto a b; plotListe listeS;; let rec polygonesEmboites n scale angle = function | 0 -> () | k -> let scale2 = scale*.cos(pi/.(float_of_int n)) and angle2 = angle +. (pi/.(float_of_int n)) in plotPolygone n scale angle; polygonesEmboites n scale2 angle2 (k-1);;