2
$\begingroup$

Suppose I want to compute $(a_1 + a_2 + ... + a_n) \mod m $. For very large values of $a_i$, I can take modulo after every operation: $ [(a_1 \mod m) + (a_2 \mod m) + ... + a_n \mod m] \mod m$ (I don't want the values to exceed their data-type's size). This doesn't work when there's a division operation in the expression.

Specifically I have this expression: $[(a-b)/5] \mod m $

which is not equal to: $ [(a \mod m) - (b \mod m)]/5 \mod m $

because after taking modulo, the numerator will not necessarily be divisible by the denominator ( a-b will always be divisible by 5).

What is the work-around to this problem?

  • 0
    @axblount I should multiply inverse modulo of 5 to $a-b$ ?? What would I do after that?2012-09-10

1 Answers 1

1

Assume that $m$ is not divisible by $5$, and let $k$ be an inverse of $5$ modulo $m$. That is, suppose that $5k\equiv 1\pmod{m}$. Then your expression can be rewritten as $(ka-kb) \bmod{m}$.

Finding an inverse of $5$ modulo $m$ requires not much work: one of $m$, $2m$, $3m$, or $4m$ is congruent to $-1$ modulo $5$. Say it is $im$. Then $k=(im+1)/5$.