Algorithme de multiplication modulaire spécifique

J’ai 3 grands nombres 64 bits: A, B et C. Je veux calculer:

(A x B) mod C 

considérant que mes registres sont de 64 bits, c’est-à-dire que l’écriture de a * b donne en réalité (A x B) mod 2⁶⁴.

Quelle est la meilleure façon de le faire? Je code en C, mais je ne pense pas que la langue soit pertinente dans ce cas.


Après avoir reçu des votes positifs sur le commentaire pointant vers cette solution:

 (a * b) % c == ((a % c) * (b % c)) % c 

laissez-moi être précis: ce n’est pas une solution, car ((a% c) * (b% c)) peut toujours être plus grand que 2⁶⁴, et le registre déborderait toujours et me donnerait la mauvaise réponse. J’aurais:

(((A mod C) x (B mod C)) mod 2⁶⁴) mod C

Comme je l’ai souligné dans un commentaire, l’algorithme de Karatsuba pourrait aider. Mais il rest un problème qui nécessite une solution distincte.

Assumer

A = (A1 << 32) + A2

B = (B1 << 32) + B2.

Quand on multiplie ceux-ci on obtient:

A * B = ((A1 * B1) << 64) + ((A1 * B2 + A2 * B1) << 32) + A2 * B2.

Nous voulons donc faire la sum de 3 chiffres et l’un d’eux est certainement supérieur à 2 ^ 64 et un autre pourrait l’être.

Mais cela pourrait être résolu!

Au lieu d’un décalage de 64 bits une fois, nous pouvons le scinder en plus petits décalages et effectuer une opération modulo à chaque décalage. Le résultat sera le même.

Ce sera toujours un problème si C lui-même est plus grand que 2 ^ 63, mais je pense que cela pourrait être résolu même dans ce cas.