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. 
 A: 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.
A: 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.
