2
$\begingroup$

What is the number of RSA fixed points, in other words how many $m$ are there such that $$m^e\equiv m \pmod{n}$$ where $n=pq$, for primes $p,q$.

I know that the answer is $(1+\text{gcd}(e^n-1,p-1))\cdot (1+\text{gcd}(e^n-1,q-1))$, but I could use some help on proving it.

$\endgroup$
4
  • $\begingroup$ I think it's $(1+\gcd(e-1,p-1))(1+\gcd(e-1,q-1))$. Do you have a citation that shows otherwise? $\endgroup$ – ogogmad May 25 '15 at 21:48
  • $\begingroup$ @user3491648 Yours seems OK, see link. $\endgroup$ – mvw May 25 '15 at 21:56
  • $\begingroup$ OP's versions seems to be for a slightly different version, see link at the bottom. $\endgroup$ – mvw May 25 '15 at 21:57
  • $\begingroup$ @mvw Makes sense, thanks. If that's the case, it should be $m^{e^n}≡m \pmod N$, and $N=pq$ (capital N). The method in that case would be the same as in my answer. $\endgroup$ – ogogmad May 25 '15 at 22:14
2
$\begingroup$

Using CRT, $$m^e \equiv m \pmod p \\ m^e \equiv m \pmod q$$

Mod p: Either $$m \equiv 0 \pmod{p}$$ or $$e \log m \equiv \log m \pmod{p-1} \iff \\ (e - 1) \log m \equiv 0 \pmod{p-1}$$ Now count the number of values of $\log m$. $\log m$ is any multiple of $\frac{p-1}{\gcd(e-1,p-1)}$. The number of multiples is $\gcd(e-1,p-1)$.

Same story mod q.

So it's $(1+\gcd(e-1,p-1))(1+\gcd(e-1,q-1))$.

[edit]

Included $m = 0$ case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.