I have a question about the calculation of RSA decryption with the help of the CRT (Chinese Remainder Theorem).

If $c$ is the crytogram, $m$ the message, $d$ the private key and $p, q$ the primes. Then in RSA with CRT they use:

$m_1 = c^d \bmod p = c^{(d \bmod (p-1))} \bmod p$ with the help of Fermat's little theorem (FLT).

But for FLT you need that $\text{gcd}(c,p)=1$ That is given if $c$ is less than $p$ because $p$ is a prime. But what is, if $c$ is bigger (because $c = m^e \bmod p*q$)? Then we can have $\text{gcd}(c,p)=p$

Does FLT also apply in this case? Or did I do something wrong?

  • 2
    $\begingroup$ Welcome to Cryptography. Check the answer by Thomas. $\endgroup$
    – kelalaka
    Commented Jul 9, 2019 at 11:12


Browse other questions tagged or ask your own question.