When taking modulo reduction by some integer $p$, one can regard this operation as reducing some number into a interval $[0,p-1]\cap\mathbb{Z}$ or another interval $(-p/2,p/2]\cap\mathbb{Z}$. I know the former usecase but do not know the latter usecase.

What is the advantage of modulo operation over $(-p/2,p/2]\cap\mathbb{Z}$ rather than $[0,p-1]\cap\mathbb{Z}$?

  • 1
    $\begingroup$ For one simple example, any number not a multiple of $3$ is $\equiv \pm 1 \pmod{3}$, so its square is $(\pm 1)^2 \equiv 1$. This would require two cases to consider, instead, if working with the non-negative remainders. $\endgroup$ – dxiv May 4 '18 at 5:12
  • 1
    $\begingroup$ If you're doing modular arithmetic by hand, the second one tends to be preferable; the numbers you get are a lot smaller. For example, if you want to compute $2^8 \bmod {19}$, it's a lot easier to notice that $2^4 \equiv -3 \pmod {19}$ and square that than it is to explicitly do the division required to reduce $256$ modulo $19$... $\endgroup$ – Micah May 4 '18 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.