Raising an expression involving modulo operator to a power.

Question

I was going through on the mathematics behind RSA. Lets say:

1. e is the encryption key
2. d is the decryption key
3. M is the plain text
4. C = M ^e mod n , where n is a product of two prime numbers is the cipher text.

Message reconstruction using decryption key

Most textbooks and links explain the reconstruction of message from the cipher text using the decryption key d as follows.

C^d ≡ M ^ed ≡ M ^kφ(n)+1 = M^kφ(n).M = (M^φ(n))^k.M = (1)^k.M = M = M mod n

Couple of questions here in the decryption equation:

• Isn't C^d = (M ^e mod n) ^d . All of the explanations just computes M ^ed and ignores mod n and just adds the mod n at the end. This must be something basic, but due to lack of background in modulo arithmetic, am failing to understand it.
• Same question applies for translating (M^φ(n))^k.M = (1)^k.M . It is understood that M^φ(n) equals 1 mod n, but how is (1 mod n) ^k equals 1.

Basically what am failing to understand is if an expression is of a form a mod n, and we raise that expression to an exponent k, (a mod n) ^k *, how do we evaluate it?

Answer 1

Several of these questions are addressed by the wikipedia article on modular arithmetic. https://en.wikipedia.org/wiki/Modular_arithmetic

Modulus distributes over addition and multiplication, and thus commutes with exponentiation. So (a^b) mod n = (a mod n)^b (Keep in mind that this equality holds considering mod n to be a function from the integers to the mod n ring; thus the equality is taking place within that ring, not within the integers. To make it true within the ring of integers, it would be (a^b) mod n = ((a mod n)^b) mod n).) You can test this out with specific numbers. For instance, if you're in base 10, then mod 10 just takes the last digit of a number. If you raise a number to a power and take the last digit, you will get the same answer as if you take the last digit, raise it to the power, and take the last digit of that number. For instance, 16² = 256. If you take the last digit of 16, that's 6. 6² = 36. 256 and 36 have the same last digit: 6.

If a = 1, then we have (1 mod n)^b = (1^b) mod n. But (1^b) = 1, so (1 mod n)^b = 1. Again, the "1" here is an element of the mod n ring. If you understand ring theory and the concept of homeomorphisms, this identity is a trivial consequence of the fact that n -> mod n is a ring homeomorphism; if you accept that Z/nZ is a ring, then 1^b must be 1, because that's an inherent property of 1 in any ring. The fact that mod n distributes over addition and multiplication also follows from n -> mod n being a ring homeomorphism.

As for numerical methods of calculating (a mod n)^b, one method is to take the binary representation of b to write a^b as a series of product and squaring. For instance, if b = 13, then b = 8+4+0+0+1, so a^b = (((a²)*a)²)²*a). After each multiplication or squaring, the result can be reduced by to the modulus function.