:: Enseignements :: ESIPE :: E3INFO :: 2015-2016 :: Algorithmique ::

Récursivité terminale

Ce TP permet de se familiariser avec l'écriture d'algorithmes simples dans leur version itérative et récursive.

Exercice 1 - Factorielle

On veut calculer la fonction factorielle d'un entier positif ou nul n, notée n!, qui est définie par
n! = 1 si n=0
n! = n * (n-1)! si n>0

Écrire une fonction récursive int factorial_rec(int n) qui traduit littéralement la définition mathématique pour calculer n!.
Écrire une fonction itérative int factorial_iter(int n) qui calcule le même résultat sans utiliser la récursion.

Remarque: n! dépasse rapidement 2³¹-1. Jusqu'à quelle valeur de n vos fonctions donnent-elles des résultats crédibles?

Exercice 2 - Suites

On veut écrire des fonctions qui affichent les n premiers entiers positifs séparés par des espaces.

Écrire une fonction itérative void increasing_sequence_iter(int n) qui affiche les entiers de 1 à n séparés par des espaces.
Écrire une fonction itérative void decreasing_sequence_iter(int n) qui affiche les entiers de n à 1 séparés par des espaces.
Écrire une fonction récursive void increasing_sequence_rec(int n) qui affiche les entiers de 1 à n séparés par des espaces.
Écrire une fonction récursive void decreasing_sequence_rec(int n) qui affiche les entiers de n à 1 séparés par des espaces.

Exercice 3 - Exponentiation modulo n

On a écrit la semaine dernière une simple fonction puissance qui calcule a^e pour a entier et e entier positif. On souhaite maintenant écrire une fonction qui calcule a^e mod n pour a < n; nous prendrons des paramètres de type long.

Reprendre votre fonction itérative naïve (qui effectue e fois la multiplication de a par lui-même) et appliquez le modulo n à chaque étape du calcul dans une fonction long exp_mod(long a, long e, long n).
Écrire une version récursive long exp_mod_rec(long a, long e, long n) de cette fonction..
Reprendre la fonction puissance de la semaine dernière qui utilise la décomposition en puissance de 2 de l'exposant e (et qui ne nécessite que log₂ e multiplications) et appliquez le modulo n à chaque étape du calcul dans une fonction long exp_mod_bin(long a, long e, long n).
Écrire une version récursive long exp_mod_bin_rec(long a, long e, long n) de cette fonction.
Comme pour l'écriture de toute fonction récursive, il faut se poser la question de comment calculer la valeur pour e à partir de la valeur d'un appel récursif pour un e plus petit. Contrairement à exp_mod_rec() qui va calculer la valeur en e à partir de la valeur en e-1, cette version binaire doit calculer la valeur en e à partir de la valeur en e/2...
L'idée est que si on connait a^e/2, alors a^e vaut
- soit a^e/2 * a^e/2 si e est pair (exemple: 3⁴ = 3² * 3²)
- soit a * a^e/2 * a^e/2 si e est impair (exemple: 3⁵ = 3 * 3² * 3²)

Exercice 4 - Chiffrement RSA

On peut utiliser les fonctions d'exponentiation modulaire dans une application pratique: le chiffrement RSA.

Sans avoir besoin de maîtriser les fondements mathématiques ni les explications précises de l'algorithme, on peut se contenter de savoir que RSA est basé sur 3 nombres entiers (p,s,n) choisis de telle sorte que pour tout entier m < n on a m^p.s mod n = m.
La sécurité de l'algorithme est basée sur la taille des nombres p, s et n (les clés) qui s'écrivent en pratique sur 1024 bits ou plus.

Une fois qu'un participant a déterminé un triplet (p,s,n), il rend public le couple (p,n) qui constitue sa clé publique. La valeur s est sa clé privée.

Pour envoyer un message à ce participant, il faut le décomposer sous la forme de valeurs m_i toutes inférieures à n. On calcule alors m_i^p mod n que l'on transmet au participant: m_i est chiffré. Il n'y a pas de manière rapide de retrouver m_i à partir de m_i^p mod n. En revanche, avec la clé privée, on peut calculer (m_i^p)^s mod n, c'est-à-dire m_i^p.s mod n qui vaut m_i: le message est déchiffré.

Pour envoyer un message textuel, on peut donc le découper en blocs de lettres qui doivent être numérisés de manière à ce que chaque valeur à transmettre (m_i) soit inférieure à n. On peut par exemple considérer que la suite de caractères d'un bloc est l'écriture d'un entier en base 256 (les coefficients sont les codes ASCII des caractères).
Pour cela, vous pourrez avoir besoin d'écrire deux fonctions:

long message_to_long(char msg[], int pos, int bloc_size) qui prend la suite de bloc_size caractères débutant à la position pos dans la chaîne de caractère msg, et qui construit la valeur msg[pos] * 256^{(bloc_size-1)} + msg[pos+1] * 256^{(bloc_size-2)} + msg[pos+2] * 256^{(bloc_size-3)} + ... + msg[pos+bloc_size-1] * 256⁰.
void long_to_message(long value, int bloc_size, char msg[], int pos) qui réalise l'opération inverse en plaçant dans msg à partir de pos les bloc_size caractères ainsi récupérés dans value.

Nous pouvons maintenant essayer de chiffrer et déchiffrer des messages.

Considérons pour l'instant que n est un entier sur 9 bits (pour cacher vos messages à votre petite soeur).
On va traiter chaque lettre du message séparément (bloc_size vaut 1), et utiliser le triplet (43, 67, 323). Quelle valeur chiffre la lettre 'A' (de code ASCII 65)?
Vérifiez le déchiffrement.
Vu la taille de la clé, une attaque exhaustive est possible. Elle revient à tenter de trouver, connaissant p et n, une valeur s qui satisfasse la propriété m^p.s mod n = m pour tout m < n... Écrivez pour cela une fonction void crack_brute_force(long p, long n) qui affichera les clés privées possibles.
Si on vous donne la clé publique (53, 323), déterminez quelle est la clé privée.
Quelle est la complexité en nombre de multiplications de votre fonction?
Considérons maintenant que n est un entier sur 17 bits (votre petite soeur a besoin de sa calculette).
On peut maintenant traiter des messages par bloc de deux lettres, et on va utiliser le triplet (52073, 5705, 96673).
La clé publique (52073, 96673) a été diffusée, et on reçoit les trois nombres 92455, 42476 et 43356, chiffrant 3 groupes de 2 lettres. Quel était le message qui vous était envoyé?
Une attaque par essai de toutes les clés est encore possible... testez-la!
Comparez les temps de calcul nécessaires pour une attaque en utilisant l'exponentiation modulaire "classique" d'une part (e multiplications de a pour calculer a^e), et l'exponentiation modulaire binaire (qui utilise la décomposition en puissance de 2 de l'exposant) d'autre part.
Problème de capacité.
Lors du calcul de l'exponentielle modulaire, on multiplie un nombre écrit sur x bits par lui-même. Le résultat est donc un nombre écrit sur 2*x bits. Pour effectuer le calcul en C avec des entiers sur 64 bits, il faut donc que x s'écrive sur 32 bits. Tous les entiers manipulés sont inférieurs au n de la clé; on doit donc avoir n ≤ 2³².
On vous donne une clé publique (p,n) = (1840404437, 1992763811). Comme n s'écrit sur 31 bits, on peut traiter le message par blocs de 3 lettres (bloc_size).
Placez sur elearning un fichier crypted_name.txt contenant la suite des valeurs qui chiffrent votre nom (complété au besoin par des espaces), avec vos fichiers C.

Exercice 5 - Somme des chiffres

On souhaite écrire une fonction qui prend en argument un entier positif n et qui calcule la somme des chiffres qui le forment.
Par exemple la somme des chiffres qui forment 912942 est 27.

Écrire une fonction itérative int sum_digits_iter(int n) qui calcule cette valeur.
Écrire une fonction récursive int sum_digits_rec(int n) qui calcule cette valeur.

Exercice 6 - Chiffre de la somme des chiffres

On souhaite maintenant écrire une fonction qui répète le calcul précédent (somme des chiffres) sur son résultat tant que ce résultat est un nombre qui n'est pas un chiffre.
Par exemple, la somme des chiffres de 912942 est 27 mais on souhaite ici obtenir 9, qui est la somme des chiffres de 27. Pour 99992, on veut que cette nouvelle fonction donne 2 qui est la somme des chiffres de 11, 11 étant la somme des chiffres de 38, lui-même est la somme des chiffres de 99992...

Écrire une fonction int digit_sum_digits_iter(int n) qui implémente cette fonction de manière itérative.
Écrire une autre fonction int digit_sum_digits_rec(int n) qui l'implémente de manière récursive.