5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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}$. $\endgroup$
    – tylo
    Commented Feb 3, 2014 at 14:38
  • $\begingroup$ @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}$. $\endgroup$
    – fgrieu
    Commented May 5, 2020 at 17:07

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How do you know it is true for $e = k-1$? $\endgroup$
    – Gretty
    Commented Feb 2, 2014 at 18:56
  • $\begingroup$ 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$. $\endgroup$ Commented Feb 2, 2014 at 20:50
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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