Sensibilisation au système cryptographique RSA

[Lilly45]

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 :)

[t.itou29]

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

Salut !
Comme tu as dit on a:
(1)
Donc (2)
Et en ajoutant (1) et (2) on obtient le résultat voulu

[Lilly45]

Salut !
Comme tu as dit on a:
(1)
Donc (2)
Et en ajoutant (1) et (2) on obtient le résultat voulu

Merci pour la réponse
Du coup c'est [x à la puissance (cd)] + x qui est congru à x modulo [p], pas x à la puissance cd tout court. Y a un truc qui m'échappe, comment on passe de
x puissance cd + x congru à x modulo [p] au résultat final recherché ?
Mais non, (x puissance cd) + x c'est congru à 0 modulo p !

[t.itou29]

Merci pour la réponse
Du coup c'est [x à la puissance (cd)] + x qui est congru à x modulo [p], pas x à la puissance cd tout court. Y a un truc qui m'échappe, comment on passe de
x puissance cd + x congru à x modulo [p] au résultat final recherché ?
Mais non, (x puissance cd) + x c'est congru à 0 modulo p !

En ajoutant les congruences ça fait soit donc c'est bien ça

[Lilly45]

En ajoutant les congruences ça fait soit donc c'est bien ça

Merci beaucoup je viens de comprendre. ^^

[Ben314]

Je doit être un peu con, mais partant de là :

(1)
Donc (2)

j'aurais rien ajouté du tout, j'aurais juste écrit que (pour utiliser des mots techniques, la relation de congruence est "reflexive" : et entraine que )

[t.itou29]

Je doit être un peu con, mais partant de là :j'aurais rien ajouté du tout, j'aurais juste écrit que ...

Effectivement c'est plus rapide !