# RSA Proof - di-mgt - modulo properties

I´m trying to follow one of the very detailed RSA Proofs given by di-mgt: "RSA theory", but unfortunately I stuck at the beginning of solution (chapter 3).

I don´t understand where the second part of (8) is coming from:

$RsaPrivate(RsaPublic(m))\ =\ (m^e\ mod\ n)^d\ mod\ n\ =\ m^{ed}\ mod\ n$

How is it reduced? Where can I find this rule?

-

You'll probably know this relation, which should be obvious if you think about it:

$$(a \bmod n) + (b \bmod n) \equiv a + b \mod n$$

This means that when using addition you do not have to reduce the operands, only the final result. However, if the final result is an operand again it needs not be reduce. This means that long chains of modular additions can be computed using normal additions with one reduction at the end.

You can see $a\times n$ as a series of additions:

$$a\times n = \overbrace{ a + \cdots + a }^{n \text{ times}}$$

You can see $a^b$ as a series of multiplications:

$$a^b = \overbrace{ a \times \cdots \times a }^{b \text{ times}}$$

So we can see $a^b$ as a very long series of additions of the base. Thus we do not need to reduce the base:

$$(a \bmod n)^b \equiv a^b \mod n$$

-