I am working on my own version of a proof of RSA and have come do a conclusion based on these simplified statements.
Given: N = pq
X ≡ 1 (mod p)
X ≡ 1 (mod q)
X ≡ 1 (mod N) by chinese remainder theorem

I have the original expression: MX ≡ M' (mod N)

When substituting X ≡ 1 (mod N) into this equation, is it correct to say that M = M' (removing the modulus) or must I say M ≡ M' (mod N)?

  • $\begingroup$ Have you created a few examples and test cases to see? $\endgroup$ – Matthew Conroy Jan 2 '11 at 21:40
  • $\begingroup$ i guess that would be a good thing to start with $\endgroup$ – dhatch387 Jan 2 '11 at 21:42
  • $\begingroup$ hm. it seems like my train of thought here is totally inaccurate... $\endgroup$ – dhatch387 Jan 2 '11 at 21:47

HINT $\ $ No,$\ $ e.g.$\ $ let $\rm\ M'\: =\: M + N\:.\ $ But the inference that $\rm\ M'\equiv M\ (mod\ N)\ $ is correct since it's a special case of the congruence product rule, viz. $\rm\ X\equiv 1\ \Rightarrow\ M\:X \equiv M\cdot 1 \equiv M\:,\:$ i.e. $\rm\ M'\equiv M\:$.

  • $\begingroup$ but I could say that M ≡ M' (mod N)? $\endgroup$ – dhatch387 Jan 2 '11 at 22:19
  • $\begingroup$ Yes, see my link to the congruence product rule. $\endgroup$ – Bill Dubuque Jan 2 '11 at 22:32

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.