1
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @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}$ $\endgroup$ Feb 21, 2013 at 1:40
  • $\begingroup$ How do you normally reduce it? $\endgroup$
    – user62753
    Feb 21, 2013 at 3:43
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user62753
    Feb 21, 2013 at 1:53
  • $\begingroup$ Yes; you can reduce the exponent $\bmod{\ \phi(M)}$ first, then proceed with the modular exponentiation. $\endgroup$
    – robjohn
    Feb 21, 2013 at 1:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .