Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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