# RSA algorithm implementation

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

• 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. Dec 9 '20 at 9:18
• 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.
– fgrieu
Dec 9 '20 at 9:42
• @fgrieu - I had asked the same question in math. I was told that CRT only helps in the unique part - not the actual splitting into 2 congruences - math.stackexchange.com/questions/4000280/… May 8 at 15:48
• @kelalaka - I had asked the same question in math. I was told that CRT only helps in the unique part - not the actual splitting into 2 congruences - math.stackexchange.com/questions/4000280/… May 8 at 15:48

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

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