Multiplication rapide modulo 2 ^ 16 + 1

Le chiffrement IDEA utilise la multiplication modulo 2^16 + 1 . Existe-t-il un algorithme pour effectuer cette opération sans opérateur modulo général (uniquement modulo 2^16 (troncature))? Dans le contexte d’IDEA, zéro est interprété comme 2^16 (cela signifie que zéro n’est pas un argument de notre multiplication et ne peut pas être le résultat, nous pouvons donc enregistrer un bit et stocker la valeur 2^16 sous la forme 0000000000000000 ). Je me demande comment le mettre en œuvre efficacement (ou si c’est possible du tout) sans utiliser l’opérateur standard Modulo.

Vous pouvez utiliser le fait que (N-1)% N == -1.

Ainsi, (65536 * a)% 65537 == -a% 65537.
En outre, -a% 65537 == -a + 1 (mod 65536), lorsque 0 est interprété comme 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; } 

Le seul problème ici est que si hi == lo , le résultat serait 0. Heureusement, une suite de tests confirme que ça ne peut pas être …

 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); } } 

Sortie: aucune

Premièrement, le cas où a ou b est zéro. Dans ce cas, il est interprété comme ayant la valeur 2 ^ 16; par conséquent, l’arithmétique modulo élémentaire nous indique que:

 result = -a - b + 1; 

, car (dans le contexte d’IDEA), l’inverse multiplicatif de 2 ^ 16 est toujours 2 ^ 16, et ses 16 bits les plus bas sont tous des zéros.

Le cas général est beaucoup plus facile qu’il n’y parait, maintenant que nous nous sums occupés du cas spécial “0” (2 ^ 16 + 1 est 0x10001):

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

Mettre ensemble:

 /* 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; }