如何避免模乘的溢出？

Question

我知道,

(a*b)%m = ((a%m)*(b%m))%m

但是有可能溢出.为简单起见,假设整数大小为2位.如果a = 2(即10 ₂)且b = 2(即10 ₂),m = 3(即11 ₂),那么%m和b%m结果为2并且在乘法后,答案为4(即100)不适合整数大小.如果从4开始考虑2-lsb,则最终答案将为0.但实际答案为1.

我该怎么做才能避免这种情况？

Answer 1

如果m-1平方不适合您的整数类型，则需要执行长乘法。对于您的两位示例，这意味着将您的两位数字分解为一对一位数字（一个高位和一个低位）并将所有四对（高乘高，高乘低，低乘高，低由低）单独。然后，您可以获得m每对的结果 mod （注意它们代表的实际位置，即四个、两个或一个）并添加结果 mod m。