# How many points in RSA, such that $m^e = m \bmod n$

For every RSA-cryptosystem, there exist some messages $$m$$, for which it holds that $$m^e \equiv m \pmod n$$

As to the question, how many such messages exist, this question has already been asked and answered here: https://math.stackexchange.com/questions/1298664/rsa-fixed-point

However, I do only understand the answer up to a certain point

Suppose that $$n$$ is only 1 prime. Then it holds that the number of unconcealable messages is $$\gcd(e-1, p-1)+1$$

This is because in $$m^e \equiv m \pmod p$$ , either $$m = 0$$ or $$m \not= 0$$. In the latter case $$m$$ can be expressed as $$g^t$$, where $$g$$ is a Generator in $$\mathbb{Z_p}$$

$$g^{t*e} \equiv g^t \pmod p$$

$$g^{t(e-1) \bmod p -1 } \equiv g^{0 \bmod p -1} \pmod p$$

$$t(e-1) \equiv 0 \pmod {p-1}$$ has exactly $$\gcd(e-1, p-1)$$ solutions, so the total number of unconcealable messages is, together with $$m=0$$ , $$\gcd(e-1, p-1)+1$$

When we now look at real RSA, which has two prime factors in its modulus, it holds that the number of unconcealable messages is $$(\gcd(e-1, p-1)+1)\cdot(\gcd(e-1, q-1)+1)$$

Why is that so? I suppose it has to do with CRT, but I just cant understand why.

Why is that so?

Well, we have $$m^e \equiv m \pmod n$$ if and only if both of the following hold:

$$m^e \equiv m \pmod p$$ $$m^e \equiv m \pmod q$$

We know (because of reasoning you accepted) that the number of solutions to the first equation (for $$0 \le m < p$$) is $$\gcd( p-1, e-1) + 1$$; we can write out the list as $$m_0, m_1, ..., m_{k-1}$$ (for $$k = \gcd( p-1, e-1) + 1$$).

Similarly, we can write out the solutions to the second equation (from $$0 \le m' < q$$) as $$m'_0, m'_1, ..., m'_{k'-1}$$ (for $$k' = \gcd( q-1, e-1 ) + 1$$).

Then, the question comes down; how many ways can we paste $$m \equiv m_i \pmod p$$ and $$m \equiv m'_j \pmod q$$ so to satisfy both equations (for $$0 \le m < n$$). It turns out (because $$p$$ and $$q$$ are relatively prime) that for a specific $$m_i, m'_j$$ pair, there is a unique value $$m$$ that satisfies both (and that's the Chinese Remainder Theorem). Each $$m$$ which corresponds a solution is formed by such a joining, and so the total number of solutions is the number of $$m_i$$'s times the number of $$m'_j$$'s; that is, $$(\gcd( p-1, e-1) + 1) \cdot (\gcd( q-1, e-1) + 1)$$

• Is it really "if and only if?" Suppose $p=61$ , $q=37$, $n=2257$, $e=31$ , then $47^{31} \equiv 47 \mod 61$ , but $47^{31} \not\equiv 47 \mod 37$ , however $47^{31} \equiv 47 \mod 2257$ – Fluctuation10111 May 5 at 15:37
• @Fluctuation10111: actually, in this case, we do have $47^{31} \equiv 47 \pmod{37}$ (both sides are equivalent to 10); however it doesn't make our list of $p=37$ because $47 > p$; we're limiting the list to values $0 \le m_i < p$. The value 47 corresponds to the combination $m_i = 10, m'_j = 47$ – poncho May 5 at 15:49
• Im apparantly blind, thank you ^^ – Fluctuation10111 May 5 at 20:18
• @Fluctuation10111: actually, I also stared at your comment for 10 minutes before I realized what was going on - you weren't the only blind guy/gal here... – poncho May 5 at 21:05