On se propose d’implanter une petite librairie d’entiers modulaires. Nous utiliserons la librairie num standard en Ocaml pour manipuler les grands nombres. On rappelle que pour utiliser la librairie num on doit soit ajouter nums.cma à la commande ocamlc de compilation, soit charger la librairie dans le “top-level” d’Ocaml en tapant:

#load "nums.cma";;

On pourra ensuite faire « open Num;; » normalement.

Nous allons implanter les structures mathématiques dans des modules Ocaml. Par exemple nous dirons qu’un ensemble est un module formé:

• d’un type support pour représenter les données
• d’opérations manipulant les données du type support:
  • une opération d’impression to_string
  • un test d’égalité equal

Nous aurons donc

module type ensemble =
sig
type carrier
val equal : carrier -> carrier -> bool
val to_string : carrier -> string
end;;

Nous pouvons alors implanter un ensemble par:

module Z:ensemble = 
struct
type carrier = big_int
let equal = eq_big_int
let to_string = string_of_big_int
end;;

Quel est le type le Z.equal? Que peut-on faire avec ce type?

Lorsque nous aurons besoin d’utiliser un ensemble dans les définitions d’algorithmes, nous pourrons utiliser le mécanisme de paramétrage des modules. Nous placerons ces algorithmes dans un module paramétré. Imaginons que nous voulions ajouter une fonction different pour nos ensembles nous pourrons alors écrire:

module Ensemble_avec_diff(E:ensemble)=
struct
type carrier = E.carrier
let equal = E.equal
let to_string = E.to_string
let different x y = not(E.equal x y)
end;;

Nous pourrons alors utiliser ces ensembles étendus grâce à la construction let module d’Ocaml:

let module Good_z = Ensemble_avec_diff(Z) ;;
let my_diff = Good_z.different;;

et my_diff est la fonction different de Ensemble_avec_diff(Z).

Le fichier anneau.ml donne les définitions des types de modules que nous utiliserons.

Écrivez le module Entiers qui encapsule le type big_int dans un module de type anneau. Vous pourrez vous aider du fichier d’interface big_int.mli que vous pourrez trouver en utilisant la commande locate.

Nous allons implanter deux méthodes d’exponentiation, évidement, vous ne devez pas utiliser les fonctions qui sont déjà définies dans big_int.mli. L’une expt qui devra prendre une valeur a du type Entiers.carrier, un int Ocaml n et retourner la valeur aⁿ. L’autre big_expt sera analogue mais prendra un big_int au lieu d’un int pour l’exposant.

Implantez expt par dichotomie en utilisant les formules a^2k+1= a.(a^k)² et a^2k=(a^k)². Pour implanter big_expt nous allons fixer un entier b qui tienne sur un int Ocaml et utiliser la formule

où q et r sont le quotient et le reste de la division euclidienne de a par b. Comme b tient sur un int, nous pourrons utiliser la fonction expt pour implanter a^r et a^b.

Généraliser les deux fonctions précédentes pour les encapsuler dans un module Puissance paramétré par un module de type anneau.

Choisissez un grand entier n et implantez le module Entiers_modulo qui implante Z/nZ. Aux fonctionalités du type anneau vous ajouterez une signature

val modulo : carrier -> big_int

qui retourne n.

Le fichier single.ml contient la définition d’un module Singleton qui permet de changer dynamiquement une valeur. Modifiez la définition du module Entiers_modulo pour prendre un module de type element (défini dans single.ml) en paramètre.

Créez deux modules Mod_1 et Mod_2 implantant deux anneaux modulaires différents.

Le fichier anneau.ml contient le type de module anneau_euclidien. Tout ce que nous avons fait utilise la division euclidienne. Comment généraliser ce qui précède pour pouvoir construire un module Anneau_modulaire qui soit paramétré par un anneau euclidien et une valeur de cet anneau?

This document was translated from L^AT_EX by H^EV^EA.