Fix $n,e\in \mathbb{Z}$ and let $C\in\mathbb{Z}_n$. How many solutions $M\in \mathbb{Z}_n$ do I have to the equation $$C \equiv M^e \;(\mbox{mod}\;n)\;?$$ This question arose from trying to solve the equation $$11\equiv M^7\;(\mbox{mod}\;187),$$ for $M<187. $
Asked
Active
Viewed 40 times
0
-
RSA algorithm ? – AgentS Nov 05 '19 at 09:38
-
Yes I was reading into RSA and out of curiosity I asked myself the quesion. – UserA Nov 05 '19 at 09:40
1 Answers
1
Let $G=Z_n$, $M \in G$ and $r = Ord_G(M)$. There are $r$ unique residues thus $r$ possible exponents $e$ for selected $M$. Note that $r \mid \lambda(n)$ where $\lambda(n)$ is the Charmichael lambda function on $n$. When $n\ \in \mathbb{P}$ (prime) then $\lambda(n) = \varphi(n)$ as it's a cyclic group generated by $\varphi(\varphi(n))$ generatos.
kub0x
- 2,117
- 1
- 15
- 25
-
But the OP doesn't assume $M$ is coprime to $n$ so $M$ may have no order. – Bill Dubuque Nov 05 '19 at 13:26
-
Well, indeed you are right! When $M$ is a non-unit, this is $\gcd(M,n)\neq 1$ there's no multiplicative order. Moreover, the product of non-units it's a non-unit again. But in RSA, taking any non-unit $M$ would reveal a non-trivial factor of the modulus, this is a very important fact as $\gcd(M,n)=p$ or $q$. – kub0x Nov 05 '19 at 13:32