Fast multiplication modulo 2 ^ 16 + 1

Question

The IDEA cipher uses multiplication modulo 2^16 + 1 . Is there an algorithm for performing this operation without a modulo-common operator (only modulo 2^16 (truncation))? In the context of IDEA, zero is interpreted as 2^16 (this means that zero is not an argument of our multiplication, and this cannot be the result, so we can save one bit and save the value 2^16 as the bit pattern 0000000000000000 ). I am wondering how to implement it effectively (or even possible) without using the standard modulo operator.

Answer 1

You can use the fact that (N-1)% N == -1.

Thus, (65536 * a)% 65537 == -a% 65537.
Also, -a% 65537 == -a + 1 (mod 65536) when 0 is interpreted as 65536

 uint16_t fastmod65537(uint16_t a, uint16_t b) { uint32_t c; uint16_t hi, lo; if (a == 0) return -b + 1; if (b == 0) return -a + 1; c = (uint32_t)a * (uint32_t)b; hi = c >> 16; lo = c; if (lo > hi) return lo-hi; return lo-hi+1; } 

The only problem here is that if hi == lo , the result will be 0. Fortunately, the test suite confirms that it really cannot be ...

 int main() { uint64_t a, b; for (a = 1; a <= 65536; a++) for (b = 1; b <= 65536; b++) { uint64_t c = a*b; uint32_t d = (c % 65537) & 65535; uint32_t e = m(a & 65535, b & 65535); if (d != e) printf("a * b % 65537 != m(%d, %d) real=%dm()=%d\n", (uint32_t)a, (uint32_t)b, d, e); } } 

Output: none

Answer 2

First, the case where either a or b is zero. In this case, it is interpreted as having a value of 2 ^ 16, therefore elementary arithmetic modulo tells us that:

 result = -a - b + 1; 

because (in the context of IDEA) the multiplicative inverse to 2 ^ 16 is still 2 ^ 16, and its lower 16 bits are all zeros.

The general case is much simpler than it seems, now that we have taken care of the special case "0" (2 ^ 16 + 1 - 0x10001):

 /* This operation can overflow: */ unsigned result = (product & 0xFFFF) - (product >> 16); /* ..so account for cases of overflow: */ result -= result >> 16; 

Combining this:

 /* All types must be sufficiently wide unsigned, eg uint32_t: */ unsigned long long product = a * b; if (product == 0) { return -a - b + 1; } else { result = (product & 0xFFFF) - (product >> 16); result -= result >> 16; return result & 0xFFFF; }