RSA algorithm implementation

Question

$$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?

Answer 1

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

Answer 2

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)}$$