我知道，
(a*b)%m = ((a%m)*(b%m))%m
但是有溢出的可能。 为简单起见，假设整数的大小为 2 位。 如果 a = 2(即 102)且 b = 2(即 102)，m = 3(即 112)，则 a%m 和 b%m 结果为 2，乘法后答案为 4(即 100)，不适合整数大小。如果从 4 开始考虑 2-lsb，则最终答案将为 0。 但实际答案是 1。
我应该怎么做才能避免这种情况？
最佳答案
如果 m-1 平方不适合您的整数类型，您需要执行长乘法。对于您的两位示例，这意味着将您的两位数分成一对一位数(高位和低位)并将所有四对相乘(高乘以高，高乘以低，低乘以高，低低)单独。然后，您可以获得每对的结果 mod m(注意它们代表的实际位置，即四、二或一)并添加结果 mod m。
关于c - 如何避免模乘法溢出？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28259832/