Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From Wikipedia(https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Proofs_of_correctness):

$m^{ed}$ ≡ $m$ $\pmod{q}$
$m^{ed}$ ≡ $m$ $\pmod{p}$
then $m^{ed}$ ≡ $m$ $\pmod{pq}$

Question:
if $m^{ed}$ ≡ $m$ $\pmod{q}$,then $q$|$m^{ed}$- $m$
if $m^{ed}$ ≡ $m$ $\pmod{p}$,then $p$|$m^{ed}$- $m$
that is to say, $m^{ed}$- $m$ is the common multiple of both $p$ and $q$

At this time, if there is $lcm(p,q)=pq$, then $m^{ed}$ ≡ $m$ $\pmod{pq}$.
However, I am not sure $lcm(p,q)=pq$ holds true or not, so how can I prove $m^{ed}$ ≡ $m$ $\pmod{pq}$?

share|improve this question
    
Congratulation for wanting a rigorous proof. Hint (the best you should get from this website for homework): it is common to assume (or explicitly require) that $p$ and $q$ are distinct, and primes; see last phrase in first paragraph here. Nitpick: you used = where you meant ≡ (twice), and did not use $\TeX$ and its operator \pmod to its full power. – fgrieu Sep 21 '15 at 16:45
1  
Got it! Both $p$ and $q$ are primes, so $pq$ is very lcm (the least common multiple) of $p$ and $q$, then $pq$ | $m^{ed} -m$ Namely, $m^{ed} ≡ m$ $\pmod{pq}$ Am I right? – Matt Elson Sep 22 '15 at 2:11
    
Yes, you solved the problem you had. Note: You can write $m^{ed}\equiv m\pmod{pq}$ as $m^{ed}\equiv m\pmod{pq}$, and $\operatorname{lcm}(p,q)=pq$ as $\operatorname{lcm}(p,q)=pq$ – fgrieu Sep 22 '15 at 5:47

If $m^{ed} \equiv m \pmod{q}$, then $q\;|\;(m^{ed}-m)$;
if $m^{ed} \equiv m \pmod{p}$, then $p\;|\;(m^{ed}-m)$;
thus $m^{ed}-m$ is a multiple of both $p$ and $q$;
thus $m^{ed}-m$ is a multiple of $\operatorname{lcm}(p,q)$.

Because both $p$ and $q$ are distinct primes, $\operatorname{lcm}(p,q)=pq$ holds;
Thus, $m^{ed}-m$ is a multiple of $pq$.

So $(pq)\;|\;(m^{ed} - m)$ clearly holds.
Thus finally, $m^{ed} \equiv m \pmod{pq}$.

share|improve this answer
    
This is the end of the proof; for a full proof, you need to establish that $m^{ed} \equiv m \pmod{q}$ and $m^{ed} \equiv m \pmod{p}$ hold. Hint: use Fermat's little theorem, and whatever relation between $e$ and $d$ you are starting from, like $ed\equiv1\pmod{\varphi(pq)}$ or $ed\equiv1\pmod{\lambda(pq)}$. – fgrieu Sep 22 '15 at 17:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.