math - 模数运算

Question

有什么方法可以计算(a mod c)*(b mod c)吗？

只知道：

• a*b
• c
• d
• ((a mod c)*(b mod c)) mod c
• (a mod d)*(b mod d)

Answer 1

不，这是不可能的。

这是一个反例：

ab = 1225 = (5)(5)(7)(7)
c = 3
d = 5000
((a mod c)(b mod c)) mod c = 1
(a mod d)(b mod d) = 1225

如果 a=25 且 b=49，则 (a mod c)(b mod c)=(1)(1)=1

如果 a=35 且 b=35，则 (a mod c)(b mod c)=(2)(2)=4