Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 2 down vote accepted

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$$

share|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.