Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know that decryption in the RSA cryptosystem works because$$D\left(C\right)\equiv C^d\equiv \left(P^e\right)^d\equiv P^{ed}\equiv P^{k\phi\left(n\right)+1}\equiv \left(P^{\phi\left(n\right)}\right)^kP\equiv P\pmod n,$$where $ed=k\phi\left(n\right)+1$ for some integer $k$, because $ed\equiv1\pmod{\phi\left(n\right)}$, and by Euler's theorem, we have that $P^{\phi\left(n\right)}\equiv1\pmod n$, because $\left(P,n\right)=1$.

However, it also works when $\left(P,n\right)\neq1$, and I am not sure how to show this. I know that if $\left(P,n\right)\neq1$, then either $P=p$ or $P=q$, where $n=pq$, but that does not seem to help much. Could someone shed some light on this for me? Thanks in advance!

share|improve this question
    
$(P,n) \neq 1$ implies that $P$ is a multiple of $p$, $q$ or $n$. –  Yuval Filmus Mar 25 '12 at 17:26
    
This might help: crypto.stackexchange.com/questions/1004/… –  mikeazo Feb 28 '13 at 15:19

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.