Return to Answer

1. $\;\gcd(e,p-1)\gcd(e,q-1)\quad$ [when $\gcd(c,n)=1\,$].
2. $\;\gcd(e,p-1\quad$ [when $q$ divides $c$; value can conflate with case 1]
3. $\;\gcd(e,q-1\quad$ [when $p$ divides $c$; value can conflate with case 1]
4. $\;1\quad$ [when $c=0$; value can conflate with cases 1/2/3]
5. $\;0\quad$ [can occur only when $c$ is not obtained by actual encryption]

1. $\;\gcd(e,p-1)\gcd(e,q-1)\quad$ [when $\gcd(c,n)=1\,$].
2. $\;\gcd(e,p-1)\quad$ [when $q$ divides $c$; value can conflate with case 1]
3. $\;\gcd(e,q-1)\quad$ [when $p$ divides $c$; value can conflate with case 1]
4. $\;1\quad$ [when $c=0$; value can conflate with cases 1/2/3]
5. $\;0\quad$ [can occur only when $c$ is not obtained by actual encryption]

_{Note: Most actual implementations of RSA decryption follow these steps, because that requires several times less computational effort than computing $m=c^d\bmod n$ directly, and parallelize better on top of that.}

That yields 5 cases for the number of solutions $m$.

1. $\;\gcd(e,p-1)\gcd(e,q-1)\quad$ [when $\gcd(c,n)=1\,$].
2. $\;\gcd(e,p-1\quad$ [when $q$ divides $c$; value can conflate with case 1]
3. $\;\gcd(e,q-1\quad$ [when $p$ divides $c$; value can conflate with case 1]
4. $\;1$ (when $c=0$; value can conflate with cases 1/2/3)
5. $\;0$ (can occur only when $c$ is not obtained by actual encryption)

_{Note: Most actual implementations of RSA decryption follow these steps, because that requires several times less computational effort than computing $m=c^d\bmod n$ directly, and parallelizes better on top of that.}

The 3×3 cases for $(u,v)$ reduce to at most 5 for the numbers $u\,v$ of solutions for $m$:

1. $\;\gcd(e,p-1)\gcd(e,q-1)\quad$ [when $\gcd(c,n)=1\,$].
2. $\;\gcd(e,p-1\quad$ [when $q$ divides $c$; value can conflate with case 1]
3. $\;\gcd(e,q-1\quad$ [when $p$ divides $c$; value can conflate with case 1]
4. $\;1\quad$ [when $c=0$; value can conflate with cases 1/2/3]
5. $\;0\quad$ [can occur only when $c$ is not obtained by actual encryption]

• Solve for $0\le x<p$ the equation $c\equiv x^e\pmod p\quad$🄐
• Solve for $0\le y<q$ the equation $c\equiv x^e\,\pmod q\quad$🄑
• Combine each possible $(x,y)$ combination to get all $m=(q^{-1}(x-y)\bmod p)\,q+y$.

• Solve for $0\le x<p$ the equation $c\equiv x^e\pmod p\quad$🄐
• Solve for $0\le y<q$ the equation $c\equiv x^e\,\pmod q\quad$🄑
• Use each possible $(x,y)$ combination to get all $m=(q^{-1}(x-y)\bmod p)\,q+y$.