Voici quelques fonctions Caml relatives au cours d'arithmétique:
OCaml
let rec quo(a,b) = if b = 0 then raise Division_by_zero else if b > 0 then if a >= 0 then if a<b then 0 else 1 + quo(a-b,b) else if b*quo(-a,b) = -a then -quo(-a,b) else -1 -quo(-a,b) else - quo(a,-b);; let rec rem(a,b) = if b = 0 then raise Division_by_zero else if b > 0 then if a >= 0 then if a<b then a else rem(a-b,b) else if rem(-a,b) = 0 then 0 else b - rem(-a,b) else rem(a,-b);; let (%) a b = rem(a,b);; (* exo 2-5 Nb chiffres d'un entier en décimal *) let rec nb_chiffres(n) = if n / 10 = 0 then 1 else 1 + nb_chiffres(n/10);; (* exo 2-6 Conversion de n (entier positif en décimal) en la liste de ses chiffres dans la base b (1 < b <= 10) *) exception Entier_negatif;; let base(n,b) = let rec base_local(k,ba,acc) = if k < 0 then raise Entier_negatif else if k < ba then acc @ [k] else base_local(k/ba,ba,acc @ [k mod ba]) in base_local(n,b,[]);; type 'a classe = {modulo:'a ; classe: 'a};; exception Classes_incompatibles;; let iso op_int a b = {modulo = if a.modulo= b.modulo then a.modulo else raise Classes_incompatibles ; classe = ((op_int) (a.classe) (b.classe)) % (a.modulo) };; let ( +% ) = iso ( + ) ;; let ( *% ) = iso ( * ) ;; {modulo =5; classe = 9%5} +% {modulo=5; classe =12%5};; let cl n a = {modulo = n; classe = (a%n)};; cl 5 12;; let c_5 = cl 5;; c_5 12;; (c_5 12) +% (c_5 9);; (c_5 12) *% (c_5 9);; 12*9 % 5;; (*----------- exo 2-7 -----------*) (* étape 1 : n -> liste de ses chiffres en base 10 *) let liste_chiffres = function |n -> base(n,10);; (* étape 2 : produit des éléments d'une liste *) exception Liste_vide;; let produit(liste) = let rec produit_local = function |[],acc -> raise Liste_vide |tete::[],acc -> tete*acc |tete::queue,acc -> produit_local(queue,tete*acc) in produit_local(liste,1);; (* étape 3 : calcul de la persistance d'un entier *) let persistance(n) = let rec pers_local(n,acc) = if n >= 0 then if n < 10 then acc else pers_local(produit(liste_chiffres(n)),1+acc) else pers_local(-n,acc) in pers_local(n,0);; (* étape 4 : recherche du + petit entier de persistance donnée (impératif) *) let petit_pers1(p) = let k = ref 0 in while persistance(!k) < p do k := !k + 1; done; !k ;; (* étape 4-bis : recherche du + petit entier de persistance donnée (récursif) *) let petit_pers2(p) = let rec petit_local(n,debut) = if persistance(debut) = n then debut else petit_local(n,debut+1) in petit_local(p,0);; exception Date_yennapas_exister;; exception Date_avant_petit_JC;; (*----------- Exo 2-9 -------------------------*) (* prévoir aussi un vérificateur de bonne date *) let zeller(j,m,a) = if (a=1582) && (m=10) && ((j>4)&&(j<15)) then raise Date_yennapas_exister else if a <= 0 then raise Date_avant_petit_JC else let semaine = [|"Samedi";"Dimanche";"Lundi";"Mardi";"Mercredi";"Jeudi";"Vendredi"|] in let mm = if m < 3 then m+12 else m in (* décalage éventuel du no de mois *) let aa = if m < 3 then a-1 else a in (* décalage éve1ntuel du no d'année *) let na = aa mod 100 (* numéro d'année *) in let s = aa / 100 (* numéro de siècle *) in let greg = if ((a<1582)||((a=1582)&&((m<10)||((m=10)&&(j<5))))) then (5-s) else (s/4 -2*s) in (* résidu à ajouter selon gregorien/julien *) let nj = j + na + na/4 +(26*(mm+1))/10 +greg in semaine.(rem(nj,7)) ;; (* pgcd en récursif *) let rec pgcd(a,b)= if a >= b then if b = 0 then a else pgcd(b,a mod b) else pgcd(b,a);; (* pgcd en itératif *) let pgcdit(a,b)= let aa = if a >= b then ref a else ref b in let bb = if a >= b then ref b else ref a in let temp = ref 0 in while rem(!aa,!bb) > 0 do temp := !aa ; aa := !bb ; bb := rem(!temp,!bb) ; done; !bb ;; (* Euclide étendu : coeff de Bézout *) let rec euclide2 a b = let rec euc(u,v,r,u',v',r') = if r' = 0 then [|u;v;r|] else let q = r/r' in euc(u',v',r',u - q * u', v - q * v', r - q * r') in euc(1,0,a,0,1,b);; (* Nb de diviseurs d'un entier *) (* récursif naïf :*) let rec nb_div_naif(n) = let rec nb_div_naif_loc(nb_a_diviser,candidat) = if candidat > nb_a_diviser then 0 else if nb_a_diviser mod candidat = 0 then 1 + nb_div_naif_loc(nb_a_diviser,candidat+1) else nb_div_naif_loc(nb_a_diviser,candidat+1) in nb_div_naif_loc(n,1);; (* Impératif naïf *) let nb_div_it(n) = let k = ref 0 in for i=1 to n do if n mod i = 0 then k := !k + 1; done; !k ;; (* Récursif amélioré *) let rec nb_div(n) = let rec nb_div_loc(nb_a_diviser,candidat) = if candidat*candidat > nb_a_diviser then 0 else if candidat*candidat = nb_a_diviser then 1 else if nb_a_diviser mod candidat = 0 then 2 + nb_div_loc(nb_a_diviser,candidat+1) else nb_div_loc(nb_a_diviser,candidat+1) in nb_div_loc(n,1);; (*----- exo 2-12 --------*) (* liste des diviseurs *) let rec liste_div(n) = let rec liste_div_loc(m,candidat) = if candidat*candidat > m then [] else if (candidat*candidat = m) then (*pas besoin d'aller voir plus loin *) [candidat] else if m mod candidat = 0 then (*on rajoute candidat et m/candidat à la liste *) (m/candidat)::candidat::liste_div_loc(m,candidat+1) else (*on passe au suivant sans rien ajouter*) liste_div_loc(m,candidat+1) in liste_div_loc(n,1);; (* somme des éléments d'une liste *) (* laisse une impression de déjà-vu... *) exception Liste_vide;; let rec som_liste = function |[] -> raise Liste_vide |tete::[] -> tete |tete::queue -> tete + som_liste(queue) ;; let parfait(n) = if som_liste(liste_div(n)) = n+n then true else false ;; let cherche_parfait(max) = let rec cherche_local(candidat,borne) = if candidat > borne then [] else if parfait(candidat) then candidat::cherche_local(candidat+1,borne) else cherche_local(candidat+1,borne) in cherche_local(1,max) ;; (*----Plus efficace------*) (* Calcule directement la somme des diviseurs de n *) let rec som_div1(n) = let rec som_div_loc(nb,candidat) = if candidat*candidat > nb then 0 else if (candidat*candidat = nb) then candidat else if nb mod candidat = 0 then candidat + (nb/candidat) + som_div_loc(nb,candidat+1) else som_div_loc(nb,candidat+1) in som_div_loc(n,1);; (* Version terminale : plus efficace *) let rec som_div(n) = let rec som_div_loc(nb,candidat,acc) = if candidat*candidat > nb then acc else if (candidat*candidat = nb) then candidat+acc else if nb mod candidat = 0 then som_div_loc(nb,candidat+1,acc+candidat+(nb/candidat)) else som_div_loc(nb,candidat+1,acc) in som_div_loc(n,1,0);; (* test de perfection *) let parfait(n) = if som_div(n) = 2*n then true else false ;; (* Recherche des parfaits <= max donné en argument *) let cherche_parfait1(max) = let rec cherche_local(candidat,borne) = if candidat > borne then [] else if parfait(candidat) then candidat::cherche_local(candidat+1,borne) else cherche_local(candidat+1,borne) in cherche_local(1,max) ;; (* récursion terminale tout en 1 plus rapide *) let cherche_parfait(max) = let rec som_div(n) = let rec som_div_loc(nb,candidat,acc) = if candidat*candidat > nb then acc else if (candidat*candidat = nb) then candidat+acc else if nb mod candidat = 0 then som_div_loc(nb,candidat+1,acc+candidat+(nb/candidat)) else som_div_loc(nb,candidat+1,acc) in som_div_loc(n,1,0) in let rec cherche_local(candidat,borne,acc) = if candidat > borne then acc else if som_div(candidat)=2*candidat then cherche_local(candidat+1,borne,candidat::acc) else cherche_local(candidat+1,borne,acc) in cherche_local(1,max,[]) ;; (*------------------------PGCD & Co-------------------------------*) (*------Algo d'Euclide I / calcul du PGCD version récursive-------*) let rec pgcd(a,b) = if a >= b then if b = 0 then a else pgcd(b,a mod b) else pgcd(b,a);; (*----- Avec espion pour compter les récursions----*) let pgcd_spy(a,b) = let rec pgcd(a,b,spy) = if a >= b then if b = 0 then (a,spy) else pgcd(b,a mod b,spy+1) else pgcd(b,a,spy+1) in pgcd(a,b,0);; (*------Fonction qui teste si 2 entiers sont 1ers entre eux--------*) let premiers_entre_eux(a,b) = if pgcd(a,b) = 1 then true else false;; (*-Euclide II / calcul du PGCD + coeff de Bézout version récursive-*) let bezout(a,b) = let rec euc(u,v,r,u',v',r') = if r' = 0 then [|u;v;r|] else let q = r/r' in euc(u',v',r',u-q*u',v-q*v',r-q*r') in euc(1,0,a,0,1,b);; (*---------Fonction qui recherche l'inverse de x modulo n---------*) exception Non_inversible ;; let inv_mod a = let b = euclide2 a.classe a.modulo in if b.(2)=1 then cl a.modulo b.(0) else raise Non_inversible;; let inv_mod2 n a = let b = euclide2 a n in if b.(2)=1 then cl n b.(0) else raise Non_inversible;; (* ------- PRIME NUMBERS ----------*) let rec est_premier1(n) = let rec test_local(t,k) = if t*t > k then true else if k mod t = 0 then false else test_local(t+1,k) in test_local(2,n);; (* en enlevant les pairs *) let rec est_premier2(n) = let rec test_local(t,k) = if (k=2) || (t*t > k) then true else if k mod t = 0 then false else test_local(t+2,k) in test_local(3,n);; (* Ératosthène *) (* On retire les multiple de n autres que n dans une liste*) let rec retmultiples (l,n) = let rec ret_loc = function | [],n,acc -> acc | t::q,n,acc -> if (t mod n = 0) && (t > n) then ret_loc(q,n,acc) else ret_loc(q,n,t::acc) in ret_loc(l,n,[]);; let rec retmultiples2 liste n = match liste with | [] -> [] | tete::queue -> if tete mod n = 0 then retmultiples2 queue n else tete::(retmultiples2 queue n);; let retmultiples3 liste n = let pred e = (e mod n != 0) in List.find_all pred liste;; (*La liste des entiers de 2 à n*) let entiers(n) = let rec listentier(m,n,acc) = if m > n then acc else listentier(m+2,n,m::acc) in listentier(3,n,[2]);; let retmultiples liste n = let pred e = (e mod n != 0) || (e=n) in List.find_all pred liste;; (*Le crible : on barre les multiples de n sauf n jusqu'à atteindre la racine carrée de n *) let crible(m)= let rec crible_rec n = if n>m then [] else if n*n>m then n::(crible_rec (n+1)) else n::(retmultiples (crible_rec (n+1)) n) in crible_rec(2);; let crible m= let rec crible_rec n acc = if n>m then acc else if n*n>m then crible_rec (n+1) (n::acc) else retmultiples (crible_rec (n+1) (n::acc)) n in crible_rec 2 [];; let crible m = let rec crible_rec n acc = match n with |n when n>m -> acc |n when n*n>m -> crible_rec (n+1) (n::acc) |_ -> retmultiples (crible_rec (n+1) (n::acc)) n in crible_rec 2 [];; (* crible 100;; *) (* lOngueur d'une liste pour compter les nb premiers inférieurs à n*) let long liste = let rec long_loc liste acc = match liste with |[] -> acc |t::q -> long_loc q (1+acc) in long_loc liste 0;; let pi n = long (crible n);; (* pi 1_000_000;; *) (* # long(crible(1_000_000));; - : int = 78498 # long(crible(10_000_000));; - : int = 664579 moi@moi-bur:~/IUT/INFO1/CAML$ ./a.out 5.37 s pour trouver le nb de premiers 78498 moi@moi-bur:~/IUT/INFO1/CAML$ ocamlopt arith_info1.ml moi@moi-bur:~/IUT/INFO1/CAML$ ./a.out 139.53 secondes pour trouver le nb de premiers < à 10000000 664579 *) let time_sn fn n msg = let start = Sys.time() in let res = fn(n) in let stop = Sys.time() in Printf.printf "%6.2f %s %n %n \n" (stop -. start) msg n res;; (* time_sn pi 1_000_000 "secondes pour trouver le nb de premiers < à ";; *) (*Décomposition en éléments simples (non terminale)*) let decompo1(n)= let rec decompotemp = function | (0 | 1),l -> [] | n,[] -> [] | n,tete::queue -> if n mod tete = 0 then tete::decompotemp(n/tete,tete::queue) else decompotemp(n,queue) in decompotemp(n,crible(n));; let decompo(n)= let rec decompotemp = function | (0 | 1),l,acc -> acc | n,[],acc -> acc | n,tete::queue,acc -> if n mod tete = 0 then decompotemp(n/tete,tete::queue,tete::acc) else decompotemp(n,queue,acc) in decompotemp(n,crible(n),[]);; (* POur enlever les doublons et n'avoir que les diviseurs *) let purge_liste(liste) = let rec loop = function | [],acc -> acc | t::[],acc -> t::acc | a::b::queue,acc -> if a = b then loop(b::queue,acc) else loop(b::queue,a::acc) in loop(liste,[]);; (*Indicatrice d'Euler : phi(k) = k * prod(p-1)/p *) let euler(n) = let rec loop = function |[],acc1,acc2 -> n*acc1/acc2 |t::q,acc1,acc2 -> loop(q,(t-1)*acc1,t*acc2) in loop(purge_liste(decompo(n)),1,1);; (*La série d'exponentiations*) let rec prap1 = function |(a,0) -> 1 |(a,1) -> a |(a,n) -> if (n mod 2 = 0) then prap1(a*a,n/2) else a*prap1(a*a,(n-1)/2);; (* version terminale *) let prap(a,n) = let rec local = function |(a,0,acc) -> acc |(a,1,acc) -> a*acc |(a,n,acc) -> if (n mod 2 = 0) then local(a*a,n/2,acc) else local(a*a,(n-1)/2,a*acc) in local(a,n,1);; let pmod(a,n,p) = let rec local = function |(a,0,p,acc) -> acc mod p |(a,1,p,acc) -> (a mod p) * (acc mod p) |(a,n,p,acc) -> if (n mod 2 = 0) then local((a mod p) * (a mod p),n/2,p,acc mod p) else local((a mod p) * (a mod p),(n-1)/2,p,(a mod p) * (acc mod p)) in local(a,n,1,p);; (*Utilisation des big zentiers*) #load "nums.cma";; open Big_int;; let badd(a,b) = Big_int.add_big_int a b;; (* la même en infixe on fera a &+ b *) let (&+) a b = Big_int.add_big_int a b;; let bmul(a,b) = Big_int.mult_big_int a b;; (* la même en infixe *) let (&*) a b = Big_int.mult_big_int a b;; let bmod(a,n) = Big_int.mod_big_int a n;; (* la même en infixe *) let (&%) a n = Big_int.mod_big_int a n;; let bquo(a,b) = Big_int.div_big_int a b;; (* la même en infixe *) let (&/) a b = Big_int.div_big_int a b;; let bsub(a,b) = Big_int.sub_big_int a b;; (* la même en infixe *) let (&-) a b = Big_int.sub_big_int a b;; let begal(a,b) = Big_int.eq_big_int a b ;; (* la même en infixe *) let (&=) a b = Big_int.eq_big_int a b ;; (* transforme un petit entier en grand entier *) let big n = Big_int.big_int_of_int n;; (* les petits entiers basiques *) let zero = zero_big_int;; let un = unit_big_int ;; let deux = big(2) ;; (* pour afficher un grand entier sous forme de chaîne *) let montre(b) = string_of_big_int b;; (* Le pgcd pour plus tard *) let bgcd a b = Big_int.gcd_big_int a b ;; (* exponentiation rapide *) let bprap(a,n) = let rec local(ba,bn,acc) = if bn &= zero then acc else if bn &= un then ba &* acc else if (bn &% deux) &= zero then local(ba &* ba, bn &/ deux , acc) else local(ba &* ba, (bn &- un) &/ deux ,ba &* acc) in local(a,n,un);; (* let (&^) a n = bprap(a,n);; *) let (&^) a n = power_big_int_positive_big_int a n;; let big_iso op_big_int a b = {modulo = if a.modulo &= b.modulo then a.modulo else raise Classes_incompatibles ; classe = ((op_big_int) (a.classe &% a.modulo) (b.classe &% a.modulo)) &% (a.modulo) };; let ( &&+ ) = big_iso ( &+ ) ;; let ( &&* ) = big_iso ( &* ) ;; let ( &&/ ) = big_iso ( &/ ) ;; let ( &&% ) = big_iso ( &% ) ;; let montre_classe b = montre b.classe;; let bcl n a = {modulo = n; classe = (a &% n)};; let bc_5 = bcl (big 5);; montre_classe ( bc_5 (big 12));; (* pour l'égalité *) let (&&=) a b = (a.modulo &= b.modulo) && ((a.classe &% a.modulo) &= (b.classe &% a.modulo)) ;; let mprap(a,n,p) = let rec local(ba,bn,acc) = if bn &= zero then acc else if bn &= un then ba &&* acc else if (bn &% deux) &= zero then local(ba &&* ba, bn &/ deux , acc) else local(ba &&* ba, (bn &- un) &/ deux ,ba &&* acc) in local({modulo = p; classe = a},n,{modulo = p ; classe = un});; let (&&^) a (n,p) = (mprap(a,n,p)).classe;; (deux &^ (big 1000)) &&^ ((big 1000),(big 10101));; (* teste l'appartenance d'un elmt à une liste*) let rec appartient = function | (el,[]) -> false | (el,tete::queue) -> if el = tete then true else appartient(el,queue);; (* teste si n est pseudo-premier de base a avec a et b des entiers *) let pseudo a n = let c = crible(n) in let rec local(a,n,i,acc) = if i >= n then acc else let bca = bcl (big i) (big a) in let bci = bcl (big i) (big (i-1)) in let p = bca.classe &&^ (bci.classe,big i) in if (p &= un) && not(appartient(i,c)) then local(a,n,i+2,i::acc) else local(a,n,i+2,acc) in local(a,n,3,[]);; pseudo 2 10000;; (*-------------------CÉSAR---------------------- *) let queue_chaine(chaine) = String.sub chaine 1 (String.length(chaine)-1);; let tete_chaine(chaine) = chaine.[0];; let string_of_char car = String.make 1 car;; let (%) a b = rem(a,b);; let decalage(n,cle) = (n- 32 + cle) % 95 + 32;; let code(car,cle) = string_of_char (char_of_int(decalage(int_of_char(car),cle)));; let rec cesar(m,cle) = if m = "" then "" else (code(tete_chaine(m),cle))^cesar(queue_chaine(m),cle);; let decalage_affine(n,a,b)= ((n-32)*a + b) % 95 + 32;; let code_affine(car,a,b) = string_of_char (char_of_int(decalage_affine(int_of_char(car),a,b)));; let rec chiffre_affine(m,a,b) = if m = "" then "" else (code_affine(tete_chaine(m),a,b))^chiffre_affine(queue_chaine(m),a,b);; let inv_decalage_affine(n,a,b)= (n - 32 - b)* (inv_mod {modulo = 95 ; classe =a}).classe % 95 + 32;; let decode_affine(car,a,b) = string_of_char (char_of_int(inv_decalage_affine(int_of_char(car),a,b)));; let rec dechiffre_affine(m,a,b) = if m = "" then "" else (decode_affine(tete_chaine(m),a,b))^dechiffre_affine(queue_chaine(m),a,b);; (*Rabin Miller *) (*Grand entier aléatoire*) exception Taille_negative;; (* nombres aléatoires (d'après le module numerix de Michel Quercia) *) (* land est le ET logique bit à bit : plus rapide que mod 1 lsl p effectue un décalage de 1 bit : plus rapide que 2^p 0xn est l'entier écrit n en base 16 On travaille donc par paquet de 16^4 renvoie un nombre < 2^n*) let nrandom n = if n < 0 then raise Taille_negative else if n = 0 then big(0) else begin let p = if n land 15 = 0 then 16 else n land 15 in let mask = (1 lsl p) - 1 in let r = ref(big(((Random.int(0xfffe)) land (mask-2))+2)) in for i=1 to (n-p)/16 do r := add_int_big_int (Random.int(0x10000)) (mult_int_big_int 0x10000 !r) done; !r end ;; (*Décomposition 2^t x s*) let dec(n) = let rec loop(s,t) = if (s &% deux) &= zero then loop( s &/ deux , t &+ un ) else [|s;t|] in loop(n &- un,zero);; (* teste a^s mod n puis les v^(2^u) *) let carre(v,n,t) = if v &= un then true else let rec loop(v,u) = if v &= (n &- un) then true else if u &= (t &- un) then false else loop( v &&^ (deux,n) , u &+ un ) in loop(v,zero);; (* renoie k, la partie entière de log_2(n) : 2^k <= n < 2^(k+1) On devra considérer des nombres inférieurs à max_float ~ 10^(308) ~ 2^(1023) *) let log2(n) = int_of_float(log(float_of_big_int(n))/.log(2.));; let blog2(n,k) = k*1024 + int_of_float(log(float_of_big_int( div_big_int n (power_int_positive_int 2 (k*1023))))/.log(2.));; exception Nombre_pair;; let rabin_miller(n) = if (n &% deux) &= zero then raise Nombre_pair else let d = dec(n) in let t = d.(1) in let s = d.(0) in let rec loop(k) = let a = nrandom (log2(n)) in if k < 64 then let v = a &&^ (s,n) in if carre(v,n,t) then loop(k+1) else false else true in loop(0);; let big_rabin_miller(n,p) = if (n &% deux) &= zero then raise Nombre_pair else let d = dec(n) in let t = d.(1) in let s = d.(0) in let rec loop(k) = let a = nrandom (blog2(n,p)) in if k < 128 then let v = a &&^ (s,n) in if carre(v,n,t) then loop(k+2) else false else true in loop(0);; (* let start = Sys.time();; let res = big_rabin_miller(bsub(power_int_positive_int 2 19937,un),19);; let stop = Sys.time();; Printf.printf "%6.2f %B \n" (stop -. start) res;; La réponse en 20 minutes moi@moi-bur:~/IUT/INFO1/CAML$ ocamlopt nums.cmxa arith_info1.ml moi@moi-bur:~/IUT/INFO1/CAML$ ./a.out 1200.31 true *) (* test de primalité pour de grands entiers On teste d'abord si n est divisible par les petits nombres premiers < 1000 *) let (&>=) a b = compare_big_int a b >= 0;; let est_premier(n) = let c = if n &>= (big(1000000)) then crible(1000) else crible(int_of_big_int(sqrt_big_int n)) in let rec test_loop = function | [] -> rabin_miller(n) | tete::queue -> if (n &% big(tete)) &= zero then false else test_loop queue in test_loop(c);; (* Génère un nombre fortement probablement premier Dans l'intervalle [2^(n-1);2^n[ *) (*renvoie un nombre entre 2^(n-1) et 2^n*) let nrandom1 n = if n < 0 then raise Taille_negative else if n = 0 then zero else begin let p = if n land 15 = 0 then 16 else n land 15 in let mask = 1 lsl (p-1) in let r = ref(big_int_of_int((Random.int(0x10000) land (mask-1)) lor mask)) in for i=1 to (n-p)/16 do r := add_int_big_int (Random.int(0x10000)) (mult_int_big_int 0x10000 !r) done; !r end ;; (* génère un fpp en faisant 10xn essais*) exception Rate;; let genere_premier n = let rec loop(k) = if k = 0 then raise Rate else let p = nrandom1 n in if est_premier(p) then (*-- montre(p),10*n-k pour voir le nb d'essais --*) p else loop(k-1) in loop(10*n);; (* #- : string = "9323965933044776889460796166024415293535391530550864193145919935327042258144900912163674609469446072081838554854780728105800118911495921310476453003669076137150734310674927109180878880209834705050148025111338966756468709557010173342077387401166199830900082541888253591201452076074749456950555323761317" *) (* RSA *) (*-Big Euclide II / calcul du PGCD + coeff de Bézout version récursive-*) let bbezout(a,b) = let rec euc(u,v,r,u',v',r') = if r' &= zero then [|u;r|] else let q = r &/ r' in euc(u',v',r',u &- (q &* u'), v &- (q &* v'),r &- (q &* r')) in euc(un,zero,a,zero,un,b);; (*---------Fonction qui recherche l'inverse de a modulo n---------*) let binv_mod(a,n) = let bb = bbezout(a,n) in if bb.(1) &= un then bb.(0) &% n else raise Non_inversible;; (*-- let p = genere_premier 1000;; let q = genere_premier 1000;; let n = p &* q ;; let phi_n = (p &- un) &* (q &- un) ;; let e = genere_premier 1000;; montre(bgcd e phi_n);; let d = binv_mod(e,phi_n);; let m = big(646566);; let crypte = m &&^ (e,n);; let decrypte = crypte &&^ (d,n);; montre(decrypte);; --*) (*-------------------------POLYNÔMES--------------------------------*) (* Polynômes à coeff entiers sans créer de module *) type 'a polynome = {coeff : 'a list ; deg : int };; let zero = 0;; let trouve_degre l = let t = List.rev l in let d = List.length l - 1 in let rec loop = function |[],k -> k |tete::queue,k -> if tete = zero then loop(queue,k-1) else k in loop(t,d);; let liste = [0;1;1;0;0;1;0;0;0;1;0;0;0];; trouve_degre liste;; let pol_of_list l = {coeff = l ; deg = trouve_degre l};; let nul = pol_of_list [zero];; let a = pol_of_list [0;1;1;0;0;1];; let b = pol_of_list [0;1;1];; let xor a b = if a <> b then 1 else 0;;