I have three N
-bit numbers, A
, B
, and C
. I cannot easily calculate (A + B) % C
but I can easily calculate A % C
and B % C
. If the modulo operation is unsigned and I know ahead of time that A + B
does not wrap around N
bits then I can instead calculate ((A % C) + (B % C)) % C
. However, is it possible to do anything for the cases where the modulo operation is signed or the addition of A
and B
might lead to a wrap-around.
It looks like there might be some confusion as to why ((A % C) + (B % C)) % C
cannot be relied upon to always work. Here is an unsigned example:
unsigned A = 0x1U;
unsigned B = 0xFFFFFFFFU;
unsigned C = 0x3U;
((A % C) + (B % C)) % C == 0x1U but (A + B) % C == 0x0U
Here is a signed example:
int A = 0x1;
int B = 0xE27F9803;
int C = 0x3U;
((A % C) + (B % C)) % C == 0x1U but (A + B) % C == -2
In math, integer division is normally rounded down towards negative infinity, and the sign of modulo is the same as the same of the "divisor" or it's zero: -10 mod 3 = 2 and 10 mod -3 = -2 (quotient rounded down to -4). In C / C++, integer division is rounded towards zero and the sign of % is the same as the sign of the "dividend" or "numerator" or it's zero, -10 mod 3 = -1 and 10 mod -3 = 1 (quotient rounded towards zero to -3). When doing finite field type math with C / C++, you need to do post correction so that the results match the mathematical definition of modulo. For example, if X % 3 = -1, then add 3 so that X mod 3 = +2.
Assuming C is positive, then the mathematical field modulo C consists of the numbers {0, 1, ... C-1}, without any negative numbers. If C was negative (this is unusual for modulo), then the field is {0, -1, -2, ... C+1}. Assuming C is positive, then if A or B is negative, it is still safe to use ((A%C)+(B%C))%C, and then post correct if the result is negative by adding C to the result.