OEF Algorithme en arithmétique
--- Introduction ---
Ce module regroupe pour l'instant 9 exercices sur quelques algorithmes en arithmétique.
On peut trouver des aides
ici.
Trouver la clé secrète de RSA
Bob a donné à Alice la clé publique RSA suivante :
,
.
Les facteurs premiers de
ont même taille (le même nombre de bits en binaire). Mais le choix de la clé privée n'a peut-être pas été bien fait, car elle est peut-être inférieure à
.
Vous allez peut-être pouvoir casser la clé en faisant tourner l'algorithme d'Euclide sur
et sur
.
En utilisant le tableau ci-dessus, quel candidat avez-vous pour la clé privée
Le candidat pour la clé privée est . La ligne suivante est extraite du tableau précédent :
Si
, que vaudrait la somme
?
Si ce n'est pas un entier, donnez sa partie entière
L'entier est-il la clé privée
Logarithme discret, baby-giant I
Soit
un nombre premier. L'élément est un générateur de
d'ordre . On désire calculer le logarithme fini d'un élément
dans la base (
sera donné plus tard). Soit
le plus petit entier supérieur à la racine carrée de . La table des
premières puissances de
dans
est
Réordonnée, elle devient Enfin, on a
modulo
Analyse de l'algorithme : Combien d'éléments de
a-t-on stockés ?
.
On prend
. - Quel est le plus petit entier
tel que
soit dans la deuxième ligne de la table :
- Calculer
- Donner le nombre de multiplications que vous venez de faire.
Logarithme discret, pas de bébé-géant II
Soit
un nombre premier. L'élément est un générateur de
d'ordre . On désire calculer le logarithme discret d'un élément
dans la base (
sera donné plus tard). Soit
le plus petit entier supérieur à la racine carrée de .
Construire le vecteur dont la
-ième composante est
mod pour
On obtient la table dans (
/):
Construire la table obtenue en arrangeant la deuxième ligne de la table par ordre croissant et en faisant les mêmes opérations sur la première ligne (on la rentrera comme une matrice : les éléments d'une ligne sont séparés par une virgule).
En effet, on obtient la matrice :
Calculer
, puis
modulo :
modulo
modulo
Analyse de l'algorithme : Combien d'éléments de
a-t-on stockés?
.
Retenons que
modulo
modulo
On prend
. Quel est le plus petit entier
tel que
soit dans la deuxième ligne de la table :
Calculez
.
Donnez le nombre de multiplications que vous venez de faire.
Comparez vous-même le coût des opérations avec les ou /2 calculs d'éléments de
que vous auriez pu avoir à faire sans la méthode précédente.
Message et lemme chinois
Vous venez de recevoir un message
inférieur à : plus précisément, vous ont été transmises les réductions de
modulo certains entiers
. Malheureusement, certaines des réductions de
sont peut-être fausses. Il y a au plus
une erreur.
deux erreurs.
Vous devez retrouvez le nombre
. Les classes résiduelles transmises sont
Quelle est la valeur du message effectivement transmis (il doit être inférieur au produit des
) :
Vous voulez appliquer l'algorithme de Bezout : sur quels nombres ?
,
Autour de l'algorithme d'Euclide I
Trouver un entier
compris entre et et tel que l'algorithme d'Euclide de
par nécessite exactement
étape.
étapes.
Elévation à la puissance
Voici les résultats partiels des calculs d'élévation à la puissance
par l'algorithme binaire de droite à gauche. - Donner l'écriture de
en binaire et sa valeur en notation décimale.
- Compléter le tableau en donnant la liste des exposants de
manquant sur la ligne
et la ligne
.
Elévation à une puissance
Calculer le nombre de multiplications et d'élévations au carré que vous devez faire en utilisant l'algorithme binaire d'exponentiation par .
Approximant de Padé
On désire calculer le
-
de
.
Pour cela, on va appliquer l'algorithme d'Euclide à
et à
En appliquant l'algorithme d'Euclide à
et à
, on obtient Calculer le
-approximant de Padé.
Ecrire 0 s'il n'existe pas
Développement de Laurent en 1/x
On fait un développement de la fraction rationnelle en
dans
.
Calculer le coefficient de
de ce développement.
The most recent version
Cette page n'est pas dans son apparence habituelle parce que
WIMS n'a pas pu reconnaître votre navigateur web.
Veuillez noter que les pages WIMS sont générées interactivement; elles ne
sont pas des fichiers
HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE.
Il est inutile pour vous de les ramasser par un programme robot.
- Description: collection d'exercices sur quelques algorithmes d'arithmétique. exercises interactifs, calcul et tracé de graphes en ligne
- Keywords: interactive mathematics, interactive math, server side interactivity, algorithmics, arithmetic,, discrete_logarithm, euclidean_algorithm, series, bezout_algorithm, rational_number