Bonjour à toutes et à tous !
Je bloque sur une question, dans un problème, depuis pas mal de temps, j'aimerais recevoir une petite piste.
Pour les amateurs de cryptographie, le système RSA c'est un système qui crypte les données informatisées pour la sécurité, c'est le plus utilisé.
1) Propriété fondamentale
n=pq est le produit de deux nombres premiers p et q distincts
On pose m= (p-1)(q-1) et on note c un nombre premier avec m
On note x un nombre entier naturel
a) Démontrer qu'il existe des nombres entiers naturels d et k tels que :
cd = km + 1 (fait)
b) Cas où x est non divisible par p
Démontrer que x à la puissance (p-1) est congru à 1 modulo [p] en utilisant le petit théorème de Fermat (fait)
En déduire que x à la puissance (km) est congru à 1 modulo [p], puis que x à la puissance (cd) est congru à x modulo [p] (fait)
Cas où x est non divisible par p (à partir de là, je suis bloquée)
Démontrer que x à la puissance (cd) est congru à x modulo [p]
c) Démontrer de façon analogue que pour tout nombre entier naturel x, x à la puissance cd est congru à x modulo q
d) En déduire que pour tout nombre entier naturel x, x à la puissance (cd) est congru à x modulo n.
Franchement je reste bloquée par le fait que x est forcément congru à 0 modulo p si x est divisible par p, du coup j'ai du mal à voir comment une puissance de x pourrait être congrue à x modulo p...
Peut être que c'est du au fait que p est premier ?
Je sais pas, je suis bloquée, aidez moi s'il vous plaît.
Bonne fin de journée à tous
-----