# Finding a value mod M

I have the following expression:

$X = 2^{(N+1)^2}-(N+1)^2-1$

And I want to find the value of X modulo M, where M < N and N is too large for me to just calculate X fully first. However, when I calculate this myself by applying the modulus everywhere:

$X = (2^{(N+1)^2 mod M} mod M-(N+1)^2 mod M-1) mod M$

I get incorrect values.

-

## 2 Answers

Modular exponentiation is a very well documented operation. To compute $b^n\bmod{m}$, you write $n$ in base $2$. Then, starting with $p=1$, for each bit in $n$ (starting at the top), square $p\bmod{m}$, and if the bit in $n$ is a $1$, multiply $p$ by the $b\pmod{m}$.

For example, let's compute $3^{136}\bmod{25}$. $136_\text{ten}=10001000_\text{two}$. $$\begin{array}{c} 1\stackrel{\text{square and \times3}}{\longrightarrow}3&\qquad\color{#C00000}{1}0001000\\ 3\stackrel{\text{square 3 times}}{\longrightarrow}21&\qquad1\color{#C00000}{000}1000\\ 21\stackrel{\text{square and \times3}}{\longrightarrow}13&\qquad1000\color{#C00000}{1}000\\ 13\stackrel{\text{square 3 times}}{\longrightarrow}21&\qquad10001\color{#C00000}{000} \end{array}$$ Thus, $3^{136}\equiv21\pmod{25}$

Combining modular exponentiation with modular multiplication should make your answer workable.

-
I am trying r = ((N+1)^2 mod phi(M)), and then the first term in my sum is therefore 2^r modulo M, correct? –  user62753 Feb 21 '13 at 1:53
Yes; you can reduce the exponent $\bmod{\ \phi(M)}$ first, then proceed with the modular exponentiation. –  robjohn Feb 21 '13 at 1:54

That is because $2^{a \pmod M} \pmod M \ne 2^a \pmod M$. You need to apply Euler's theorem $2^{\phi(n)} = 1 \pmod n$ in the first element of your sum.

-
@user62753 you can't reduce the exponent modulo m, though if 2 and m are coprime you can reduce it by the multiplicative order of 2 modulo m, or in general by any integer k satisfying $2^k\equiv \text{ 1 mod m}$ –  Ethan Feb 21 '13 at 1:40
How do you normally reduce it? –  user62753 Feb 21 '13 at 3:43