1
$\begingroup$

$$m^{ed} \equiv m \bmod n$$ $n =pq$, so by Chinese Remainder Theorem it is equivalent to $$m^{ed} \equiv m \bmod 𝑝, m^{ed} \equiv m \bmod q$$ where $n=p\cdot q$

So how did 2 come from 1 by the Chinese remainder theorem? I know Chinese algorithm but How did $m^{ed} \equiv m \bmod p$ and $q$ come?

$\endgroup$
2
  • $\begingroup$ It is a useful way of using the CRT, instead of given two modular equations on $p$ and $q$ to solve on $pq$, now we construct it in $\bmod p$ and $\bmod q$ than solving it. This helps us to have approximately 4x speed up during the calculations. $\endgroup$ – kelalaka Dec 9 '20 at 9:18
  • $\begingroup$ Hint: replace $m^{ed}$ by $x$ (and $n$ by $p\,q$ as per their definition in RSA). Do you better recognize the Chinese Remainder Theorem? Picky note: when the question writes "so by Chinese Remainder Theorem" it is forgotten an hypothesis in the CRT; namely, $\gcd(p,q)=1$. That's part of why we use distinct primes in RSA. $\endgroup$ – fgrieu Dec 9 '20 at 9:42
0
$\begingroup$

Observe that for any $n$, $l$, as long as $l | n$, any equivalence $a \equiv b \pmod n$ also holds mod $l$: $a \equiv b \pmod l$ . To fully see this, we can write

$$ \begin{align*} a &\equiv b \pmod n \\ \Leftrightarrow \\ a &= b + kn \\&=b + ktl \quad(\text{since } l|n\text{, so } n = tl)\\ \Rightarrow\\ a &\equiv b \pmod l \end{align*} $$

So you could solve $m^e \pmod p \equiv a$ and $m^e \pmod q \equiv b$, then use CRT to get $m \pmod n$.

$\endgroup$
0
$\begingroup$

as @fgrieu mentioned above,

  • CRT states that : if m and n be two integers such that gcd(m,n)=1 then we have

-$${ f: Z_{mn} -> Z_m \cdot Z_n}$$ defined by ${f(x)=(x mod m, x mod n)}$ is a ring isomorphism

-$${Phi(mn)=Phi(m)Phi(n)}$$

$\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.