Déchiffrement

Notez qu'il n'est pas trivial de retrouver $M$ à partir de $M^\prime$ et de $(C, PQ)$. La clé privée est un couple $(C^\prime, N)$ tel que pour tout message $M$,

$$(M^C)^{C^\prime} \equiv M \pmod N$$

Alors on déchiffre $M^\prime$ en calculant

$$M \equiv (M^\prime)^{C^\prime} \pmod N$$

Ici on a $C^\prime = 23$. On constate que $M \equiv 7^{23} \equiv 13 \pmod{55}$. La question que l'on est invité à se poser est : comment on trouve $C^\prime$ ?