OEF Arithmétique: Application des théorèmes en TS --- Introduction ---

1. Autour de Bezout: Trouver les coefficients de Bezout
2. Autour de Gauss: Résoudre une équation linéaire modulaire (fait intervenir Bezout)
3. Autour de Fermat: Exercices de cryptage

Théorème de Bezout 1

Trouver des entiers relatifs et tels que :

Théorème de Bezout 2

Peut- on trouver des entiers relatifs et tels que :

Théorème de Bezout 3

Connaissant une solution particulière (,) de l'équation diophantienne:

Théorème de Bezout 4

Connaissant une solution particulière (,) de l'équation diophantienne:

Chiffrement affine

On assimile les 26 lettres de l'alphabet aux nombres .

On code alors un nombre ainsi:

1. Chiffrer le mot :
2. Déterminer une fonction de déchiffrage de dans lui-même, telle que:

   doit être de la forme avec

3. Déchiffrer le mot :

Chiffrement de Lester Hill

On assimile les 23 lettres de l'alphabet aux nombres .

La fonction de codage agit sur des couples de nombres choisis dans Dans cet exemple, on a :

1. Chiffrer le mot :
2. Déterminer une fonction de déchiffrage de dans lui même, telle que:

   sous la forme:

   + +
3. Trouver un couple d'entiers relatifs avec tel que et
4. Déchiffrer le mot :

Chiffrement à clé secrète

On dispose d'une clé qui peut être un mot, une phrase,etc. et celle-ci fournit une suite de nombres: la liste des rangs dans l'alphabet dans l'ordre des lettres qui la forment.
Par exemple, fournit la suite .
Avec cette clé, pour chiffrer un texte, on remplace chaque lettre par son rang dans l'alphabet (avec 0 pour A, 1 pour B, et 25 pour Z), on ajoute au rang de la première lettre, au rang de la deuxième lettre, au rang de la troisième lettre, au rang de la quatrième lettre et on recommence avec la même clé, au rang de la cinquième lettre, etc.
On obtient les rangs des lettres qui remplacent.
Ces rangs sont les restes de la division de par 26, varie pour chaque lettre en fonction de la clé.
L'intérêt est qu'une lettre n'est pas toujours codée de la même façon.

1. Chiffrer le message avec la clé .
   message crypté=
2. Déchiffrer le message avec la clé .
   message décrypté=

Chiffrement à clé publique RSA

On considère les nombres premiers et , ainsi que le nombre .

1. Déterminer un entier inférieur à 15, premier avec
2. Déterminer un entier naturel tel que soit divisible par

On a choisi les entiers et .
On veut coder la lettre correspondant au nombre

1. Calculer le reste de la division de par
2. Calculer le reste de la division de par

Autour du théorème de Gauss 1

1. Résoudre l'équation de congruence:

   1 mod

   Donner la valeur de appartenant à l'ensemble .
2. Résoudre l'équation de congruence:

   mod

   Donner la valeur de appartenant à l'ensemble .

Autour du théorème de Gauss 2

Résoudre l'équation de congruence:

mod

Autour du théorème de Gauss 3

L'équation de congruence:

mod

mod