5

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?

fgrieu
  • 140,762
  • 12
  • 307
  • 587
Gretty
  • 239
  • 1
  • 5
  • 9
  • 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 03 '14 at 14:38
  • @tylo: unless the calculation/equation involves division. E.g. $\displaystyle\frac 22=1$ holds in $\mathbb{Z}$, but is undefined/does not hold in $\mathbb{Z}/2\mathbb{Z}$. – fgrieu May 05 '20 at 17:07

3 Answers3

4

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

$$(ab)\textrm{ mod } n = \big((a\textrm{ mod } n)\cdot(b\textrm{ mod } n)\big)\textrm{ mod } n$$

Write $a=k_an+r_a$ and $b=k_bn+r_b$ and thus $a \textrm{ mod } n = r_a$ and $b \textrm{ mod } n = r_b$. Plugging into the left hand side will give you:

\begin{align}\big((k_an+r_a)(k_bn+r_b)\big)\textrm{ mod } n &= \big((k_a k_b n + k_a r_b+ k_br_a )n + (r_a r_b)\big)\textrm{ mod } n \\ &= (r_a r_b)\textrm{ mod } n\end{align}

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 r_b ) \textrm{ mod } n$. This shows the equality which is what you're looking for.

Viewing the exponentiation $m^e \textrm{ 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.

eykanal
  • 103
  • 4
DrLecter
  • 12,547
  • 3
  • 43
  • 61
3

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

poncho
  • 147,019
  • 11
  • 229
  • 360
  • How do you know it is true for $e = k-1$? – Gretty Feb 02 '14 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 02 '14 at 20:50
1

Write

$$ m = pn+r \Rightarrow \ m \bmod \ n =r \Rightarrow r^e = (m \bmod \ n)^e \quad (1) $$

Using the Binomial Theorem,

\begin{align} \ m^e = (pn+r)^e & = [(pn)^e+e\cdot(pn)^{e-1} \cdot r+\cdots+ e \cdot (pn) \cdot r^{e-1} + r^e] \\ & = [(pn)^{e-1}+e\cdot(pn)^{e-2} \cdot r+\cdots+ e \cdot r^{e-1}] \cdot (pn) + r^e \\ &= d \cdot n + r^e \end{align}

where $$ \ d = [(pn)^{e-1}+e\cdot(pn)^{e-2} \cdot r+ \cdots + e \cdot r^{e-1}] \cdot p $$

So, $$ \ m ^e \bmod \ n = ( d \cdot n + r^e ) \bmod \ n = r^e \bmod \ n \ $$

Using $\ (1)$,

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

kelalaka
  • 48,443
  • 11
  • 116
  • 196
Kostas Letros
  • 11
  • 3