Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

If $e$ is a natural number, then this is true:

$$m^e \bmod\ n = (m\bmod\ n)^e\bmod\ n$$

This is often used when encrypting, especially with RSA, since one can avoid directly calculating $m^e$, which can be a very big number.

However, I haven't been able to find any documentation/proof for this conjecture, can anyone give a source or explain it?

share|improve this question
    
For every possible integer calculation the following holds: If an euqation is true in $\mathbb{Z}$, then it is also true in every $\mathbb{Z}/n\mathbb{Z}, n \in \mathbb{N}$. –  tylo Feb 3 at 14:38
add comment

2 Answers

up vote 2 down vote accepted

That is not a conjecture, that is basic number theory and follows from the fact that

$$(a \cdot b)\mod n = ((a \mod n)\cdot(b\mod n))\mod n$$

Write $a=k_a\cdot n+r_a$ and $b=k_b\cdot n+r_b$ and thus $a \mod n = r_a$ and $b \mod n = r_b$ and then plugging into the left hand side will give you:

$((k_a\cdot n+r_a)\cdot (k_b\cdot n+r_b))\mod n = ((k_a\cdot k_b \cdot n + k_a \cdot r_b+ r_a \cdot k_b)\cdot n + (r_a \cdot r_b))\mod n = (r_a \cdot r_b)\mod n$

The last step is because any multiple of $n$ clearly yields a zero remainder when divided by $n$.

Plug into the right hand side gives you $(r_a \cdot r_b ) \mod n$ and this shows the equality and that's what you want to have.

Viewing the exponentiation $m^e \mod n$ as $(m \cdot \ldots \cdot m) \mod n$ (multiplying $m$ with itself $e-1$ times), then you have what you are looking for.

share|improve this answer
    
Thank you very much, now it all makes sense. –  Gretty Feb 2 at 20:19
add comment

You can arrive at a simple proof by induction, using the more basic theorem that:

$$a \times b \bmod n = (a \bmod n) \times (b \bmod n) \bmod n$$

With that, then the inductive proof goes as:

  • It is true for $e = 1$. This can be seen as:

$$m^1 \bmod n = (m \bmod n)^1 \bmod n$$

  • If it is true from $e = k-1$, then it is true for $e = k$. This is, if we posit that:

$$m^{k-1} \bmod n = (m \bmod n)^{k-1} \bmod n$$

then, if we multiply both sides by $m \bmod n$, we get:

$$m^{k-1} \times m \bmod n = (((m \bmod n)^{k-1} \bmod n)\times m \bmod n$$

or (using the basic theorem on the right side):

$$m^{k} \bmod n = (m \bmod n)^{k-1} \times (m \bmod n) \bmod n$$

or

$$m^{k} \bmod n = (m \bmod n)^{k} \bmod n$$

share|improve this answer
    
How do you know it is true for $e = k-1$? –  Gretty Feb 2 at 18:56
    
This is a proof by induction. We know it is true for $e = 1$. Using the formula in the answer, we can then prove it is true for $e = 2$ as well, and then for $e = 3$ etc. No matter how large $e$ gets, we might prove that the formula is true for $e + 1$ as well. Hence, by induction, it is true for all integer values of $e$. –  Henrick Hellström Feb 2 at 20:50
add comment

Your Answer

 
discard

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.