0
$\begingroup$

know some rules for modular arithmetic expressions, for example,

  1. $A+B=C\implies ((A\bmod M) + (B\bmod M))\bmod M = C\bmod M$.

2.$A\times B=C\implies $((A\bmod M)\times (B\bmod M))\bmod M = C\bmod M.

(A$, $B$, $C$, and $M$ are just constant arbitrary integers)

But I did not understand the following one $A - B = C \implies ( (A\bmod M)-(B\bmod M)+kM)\bmod M = C\bmod M$ for some value $k.

I am interested because, as I know, such methods are used in computing hash values of strings and generally related with string search methods. My question is, what does k$ do in this case? Can we use arbitrary value of $k$? or how to calculate which value of $k$ is relevant for such calculation? Thanks a lot.

2 Answers 2

1

Do you know the meaning of modular arithmetic? If so then you will know that when you do any addition/subtraction/multiplication you might not get an answer that lies in the range 0,1,2,..., M-1 so you might have to manipulate your answer by a multiple of M

  • 0
    No, notice that $k$ only comes up in the context $kM$, so it's a multiplier of $M$, not a multiple of $M$.2012-03-09
1

$M\equiv 0 \pmod{M}$, so $M$ acts like zero in this type of expression. So your expression is demonstrating the modification $ A-B=C \rightarrow A-B+k*0 = C $ from which it should be clear that $k$ can be arbitrary.