# Problem with calculating the correct value for $(p-1)*(q-1)$?

I came to a problem when calculating some values for RSA encryption task.

So the data I have is this:

$$e*d=81$$

$$C=5$$

Now I have to calculate the original message($$m$$) and I have an issue because I can see what the solution for $$m$$ should be, but I get a different answer.

So far, I was able to figure out that $$e=27$$ and $$d=3$$.

Now I should calculate $$m=(p-1)*(q-1)$$ with the equation: $$e*d \bmod m = 1$$.

But the solution I have from this example says that $$m=40 \rightarrow 4*10$$ which gives us $$p=5$$ and $$q=11$$.

Now my question is why is $$40$$ correct and not $$m=20 \rightarrow 2*10 \rightarrow p=3$$ and $$q=11$$, which is what I got?

• The question's givens do not allow to "figure out that $e=27$ and $d=3$", and allow several solutions. Something must be missing! Additionally, is $ed\bmod((p-1)(q-1))=1$ precisely the requirement? Assuming $p$ and $q$ are distinct primes, the necessary and sufficient condition for RSA to work is $ed\bmodλ=1$ with $λ=\operatorname{lcm}(p-1,q-1)$, and many authors require $d=e^{-1}\bmodλ$ or $d=e^{-1}\bmodφ$ where $φ=(p-1)(q-1)$, rather than $ed\bmodφ=1$. – fgrieu Jan 11 at 4:41

It turns out that the necessary and sufficient conditions on $$p, q$$ is that $$p-1, q-1$$ are factors of $$ed-1$$; hence we know that $$p, q \in \{ 3, 5, 11, 17, 41 \}$$ (as those are the primes that meet this criteria), and any such combination of distinct $$p, q$$ would work (we also know that $$pq > c$$, however all combinations meet this criteria); by work, I mean that $$(m^e)^d \equiv m \bmod{pq}$$ for all messages $$m$$. Now, with some combinations, the $$e, d$$ combination might not be minimal; however nonminimal $$e, d$$ values do happen in practice.
As both $$p, q = 5, 11$$ and $$p, q = 3, 11$$ meet the above criteria, both lead to valid answers. If the original question did not add any additional information, well, they did not specify the question sufficiently.
• @masterdodo: as for whether the combination has to be minimal, well, that's something that the poser of the question would need to answer. As for why the above criteria work, well, $(m^e)^d \equiv m \pmod{pq}$ iff $m^{ed} \equiv m \pmod p$ and $m^{ed} \equiv m \pmod q$; the last two are true for all $m$ iff $ed \equiv 1 \pmod{p-1}$ and $ed \equiv 1 \pmod{q-1}$; the later are equivlant to the statement $p-1, q-1$ are both factors of $ed-1$ – poncho Jan 11 at 2:40