Codage par exponentiation arithmétique

[Impiger]

Bonjour

J'ai un gros problème sur un DM de Spé Maths qui reprend les congruences , PGCD et Bézeout et Gauss, mais j'ai pas mal de difficultés.

Données:
-P est un nbr à coder
-p est un nombre premier tel que P plus petit que p
-e entier naturel premier avec p-1 (e est la clé du codage)
-d et k entiers naturels tels que de=k(p-1)+1 (d est la clé du décodage)
-pour coder P on calcule C : C congru à P^e [p]
-pour décoder il suffit de calculer C^d [p] car C^d congru à P [p]

1) Démontrer que P^(p-1) est congru à 1 [p]

2) Démontrer que P^z(p-1) est congru à P [p] où z entier naturel

3)a) Démontrer qu'il existe des entiers relatifs u et v tels que eu + v (p-1) = 1

b) Dire pourquoi on peut choisir une valeur de u notée d telle que
0< d< p-1

c) en déduire que ed=k(p-1)+1 où k entier naturel



J'ai réussi toutes les questions mais je sèche à la 3b) parce que je ne vois aucun rapport et je ne sais pas sur quoi partir.

Merci d'avance

[Ben314]

Salut,
Pour la 3)b), l'idée est "d'améliorer" la réponse de la 3)a), c'est à dire non seulement montrer qu'il existe une solution uo, vo de l'équation
eu + v (p-1) = 1
mais en plus déterminer toutes les solutions de cette équation (en fonction de la solution de départ uo,vo) pour montrer qu'il y en a une qui vérifie ce que l'on te demande.

[dudumath]

dans la question a) tu as montré qu'il existait u et v qui allaient.
En fait, il en existe une infinité, par conséquent tu peux en choisir un entre 0 et p-1 (et il est facile de connaitre son expression par résolution de l'équation de diophante précédente)

[EDIT: désolé Ben314, tu as dégainé plus vite que moi]

[Impiger]

Mais, tout en résolvant l'équation diophantienne à partir des 2 solutions supposées u et v, je ne vois pas comment on arrive à l'encadrement
ou d remplace u : 0 < d < p-1

parce que j'ai :

eu + v (p-1) = 1 a et b soultions à trouver
ea + b (p-1) = 1 Donc e(u-a) = (p-1) (b-v)

et donc u-a = k (p-1) et b-v = k e
a = u-k(p-1) b = ke +v

[Ben314]

Tu n'as plus qu'a 'constater' que, si on choisis k de manière convenable,
a = u-k(p-1)
sera égal au reste de la division euclidienne de u par p-1 et donc sera bien un nombre entre 0 et p-2 (compris)

[Impiger]

je n'aurais jamais pensé au reste de la division euclidienne , merci.
Mais à ce moment -là, comment fait -on pour exclure le 0. Car le reste de la disvion euclidienne pourrait être nul, or, ici on veut 0

[Impiger]

je veux dire 0

[Ben314]

Si le reste de la division est égal à 0, il suffit d'augmenter k de 1 pour trouver a=p-1 à la place de a=0...

[Impiger]

D'accord !
L'ennui, c'est que je bloque encore sur la suite de l'exo. Je ne le trouve vraiment pas facile.

On code un message :
-on code comme ceci : A=00, B=01, C=02...
-Les lettres sont groupées par 2. Donc P est un bloc de 4 chiffres.
- p= 2633 et e=29

1) Il faut coder le mot DECODAGE: c'est-à dire coder
0304 0214 0300 0604
ça , je crois que j'y arrive en calculant 0304^29 [2633] etc.

2) mais là j'ai un gros problème:
En appliquant l'algorithme d'Euclide au couple (2632;29) démontrer que d=2269 e=29
Puis décoder le mot de 4 lettres :
1566 1846

Parce qu'en appliquant le théorème d'Euclide, j'obtiens:
4 x 2269 - 363 x 29 =1 et pas de 2269

et puis pour décoder , je veux bien calculer C^d [p],
mais c'est tellement grand,que ça ne marche pas, je fais :1566^2269 [2263] ??

[Ben314]

Parce qu'en appliquant le théorème d'Euclide, j'obtiens:
4 x 2269 - 363 x 29 =1

Si t'as trouvé ça, c'est impec. t'as plus qu'a multiplier par 2269 pour obtenir une formule du type de celle que tu veut puis regarder la partie "théorique" pour voir comment faire diminuer le 4x2269 (ainsi que le 363x2269)

je veux bien calculer C^d [p], mais c'est tellement grand,que ça ne marche pas, je fais :1566^2269 [2263] ??

De toute façon, même si ta machine arrivait à calculer 1566^2269, elle ne calculerais que les 10 ou 12 chiffres les plus significatifs or, pour avoir le reste de la division par 2263, il faut tout les chiffres...
Deux soluces :
1) tu cherche un programme de 'calcul formel' sur le net qui accepte de faire des calculs exacts sur les nombres de grande taille
2) tu fait un calcul 'de proche en proche' :
a) tu calcule 1566^2 et tu regarde le reste de la division par 2263
b) tu élève ce reste au carré et tu regarde le reste de la division par 2263
(c'est en fait le reste de 1566^4)
c) tu élève ce reste au carré et tu regarde le reste de la division par 2263
(c'est en fait le reste de 1566^8)
etc...
enfin tu écrit 2269 comme une somme de puissance de 2 et tu n'as plus qu'a faire un produit
(Cette technique est celle utilisé par les ordinateurs pour crypter/décrypter)

[Impiger]

Pour ce qui est du décodage, j'ai compris : le message codé, très original était CECI.
Mais, par contre, pour l'Algorithme d'Euclide, je pense avoir compris mais n'en suis pas certain.

A partir de
1= - 363x29 + 4x2632 (J'avais fait une erreur de frappe.)
1= ed - k (p-1)
1= 29d - k 2632

On a donc
29 (d + 363) = 2632 ( 4 + k)

et on a d = 2632 j -363
Si j = 1, alors d= 2269; Faut-il prendr j=1. ou est-ce qu'en fait l'énoncé prend tout simplement la plus petite valeur strictement positive ? 9a voudrait dire qu'il y d'autre "clés de décodage" ?

[Ben314]

Si j = 1, alors d= 2269; Faut-il prendr j=1. ou est-ce qu'en fait l'énoncé prend tout simplement la plus petite valeur strictement positive ? 9a voudrait dire qu'il y d'autre "clés de décodage" ?

Il y a effectivement une infinité de clé de décodage (comme toujours avec les congruences) et en général, on prend effectivement la plus petite positive.

[Impiger]

C'est génial. J'ai enfin fini, en ayant compris.
Merci infiniment Ben314, c'était super sympa.
Et joyeux Noël