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

j
j
Réordonnée, elle devient
Enfin, on a

equiv modulo

Analyse de l'algorithme : Combien d'éléments de a-t-on stockés ? .
On prend .

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 (ZZ/ZZ):
j
j
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
modulo mod  
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 ?
,
L'algorithme d'Euclide appliqué à et donne les équations suivantes
Quel est le message ?

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.

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.
Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

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.