1

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.

user62753
  • 135

2 Answers2

1

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.

marty cohen
  • 107,799
  • @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 Splaver Feb 21 '13 at 01:40
  • How do you normally reduce it? – user62753 Feb 21 '13 at 03:43
0

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.

robjohn
  • 345,667
  • 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 01:53
  • Yes; you can reduce the exponent $\bmod{\ \phi(M)}$ first, then proceed with the modular exponentiation. – robjohn Feb 21 '13 at 01:54