In RSA Algorithm, we have public key(e,n) and private key(d,n).
Sender side we encrypt plain text P as an integer between 0 and n-1 as follows:
$P^{e}modn$
and send it.
At receiver side, we do the following:
$(P^{e}modn)^{d}modn = P^{ed}modn$
$P^{ed}modn= P$
But according to Euler's Theorem:
The following equation holds if 'a' and 'n' are coprimes:
$a^{\phi (n)t+1)}modn= a$
So, what I am confused about is that while encrypting the message P we are taking it as as integer between 0 and n-1. So, the P may not be coprime to n. Then how does the algorithm work?
