# How do I find nine messages which are unchanged by RSA encryption using the public key $(3869, 3)$.

I understand how RSA crytosystem works, however I am not sure how to apply it to answer these questions. Can someone explain please?

Let $N=3869$ and be the product of two distinct unknown odd prime numbers $p$ and $q$ such that $(p − 1)(q − 1)$ is not divisible by $3$. Show that there are exactly nine messages which are unchanged by RSA encryption using the public key $(N, 3)$.

Also explain how to find p and q if at least four of these messages are known.

If it is unchanged by the private key, then surely it is also unchanged by the public key (and vice versa). Thus, you must find the number of solutions to $m^3=m\pmod{N}$. This amounts to solving two different equations $m^3=m\pmod{p}$ and $m^3=m\pmod{q}$ and combining them using the Chinese remainder theorem. In each case, $m=0$ is a solution, and also the two solutions to $m^2=1$ (modulo the prime). Hence, there are nine solutions modulo $N$.
I haven't solved the next part, but it might be useful to note that having four solutions means, by the Pigeonhole principle, that there will be enough messages so that they will give at least two different values modulo both $p$ and $q$.
• I do not understand why we need to solve $m^{3}$=$m$ ($mod$ $N$). Where does the 3 come from in particular? Also from your response am I right in saying m=0,1 and -1 are three of the messages? If so, how do you find the other 6. Can you explain please? – Jed May 3 '15 at 19:11
• The $3$ comes from the public key (this is decrypting the message $m$). And $0,-1,1$ are three of the messages modulo $p$ and modulo $q$: use the Chinese remainder theorem to get all nine from these. – Kyle Miller May 3 '15 at 19:53
• In your post you said $N$ is the product of two odd primes $p$ and $q$. Since they are coprime, there are $a$ and $b$ such that $ap+bq=1$. Then, $m=0,ap,-ap,bq,ap+bq,-ap+bq,-bq,ap-bq,-ap-bq$ are the messages. – Kyle Miller May 3 '15 at 22:24