Travaux pratiques du module I32.

Algorithmique arithmétique,

 décembre 2001.

    L'objectif de ces travaux pratiques est d'explorer numériquement la primalité des nombres de la forme n! + 1,  où  n!  désigne la factorielle de n i.e. le produit des n premiers entiers non nuls.

Dans vos implantations, les nombres seront représentés dans une base arbitraire. Vous utiliserez les définitions et déclarations suivantes :

#define  MAX 100
typedef  unsigned  int CHIFFRE;
typedef  unsigned int NOMBRE[MAX];
unsigned int BASE;

PREMIERE PARTIE

[ 0 ] Ecrire la procédure  INC( NOMBRE z) pour incrémenter le nombre z dans la base choisie.

[ 1 ] Ecrire la procédure CMUL( NOMBRE z, CHIFFRE c)  qui calcule  le produit du nombre z par le chiffre c dans la base choisie.

[ 2 ] Ecrire la procédure BMUL( NOMBRE z)  qui calcule  le produit du nombre z par la base.

[ 3 ] Estimer le nombre de chiffres en base n du nombre  n! + 1.

[ 4 ] Calculer 100! + 1 en base 100.

DEUXIEME PARTIE

[ 5 ] Ecrire la procédure  MIX( NOMBRE z, NOMBRE x, CHIFFRE c) qui effectue le calcul  z := z + x * c.

[ 6 ] Ecrire la procédure REDUCTION( NOMBRE z, NOMBRE r) qui calcule z modulo r sachant que la taille de z est au plus celle de r augmentée de 1.

[ 7 ] Déduire des deux questions précédentes  une procédure pour calculer x*y modulo r lorsque  x< r  et y<r . Quelle est a complexité ?

TROISIEME PARTIE

[ 8  Ecrire une procédure EXP( NOMBRE z, CHIFFRE c, NOMBRE r) pour calculer z^c modulo r.
 

Le petit théorème de Fermat affirme qu'un entier n > 1 est premier si et seulement si a^(n-1) = 1 modulo n pour tout entier a compris entre 0 et n.

[ 9 ] Faire une démonstration.

 On dit qu'un residu a modulo n est un témoin de la non primalité de n si a^(n-1) est différent de 1 modulo n.

[ A ]  Ecrire la fonction TEMOIN(CHIFFRE a, CHIFFRE n)   qui calcule  R := n! + 1 puis a^(n!) modulo R et qui  renvoie VRAI si a est un témoin de non primalité de R et FAUX  sinon.

[ B ] Evaluer la complexité de la fonction TEMOIN(a, n) en fonction de n.

[ C ] Faire une expérience numérique pour n aussi grand que possible.  Donner une formule pour le  temps d'exécution de cette  fonction.