模运算性质(A*B)%m=(A%m*B%m)%m在大数取模算法中的应用疑问

核心模运算性质 #

你提到的乘法分配性质：(A*B)%m = (A%m * B%m) %m，结合加法的模运算性质(A+B)%m = ((A%m)+(B%m))%m，就是大数取模算法的核心依据。

算法原理拆解（以12345%100为例） #

先把数字12345拆解成逐位构建的数学表达式：
12345 = (((((0 * 10) + 1) * 10) + 2) * 10 + 3) * 10 + 4) * 10 + 5

我们用模运算性质一步步计算12345%100：

1. 初始化结果res = 0
2. 处理第一位数字1：
   res = (0 * 10 + 1) % 100 = 1
   这里利用(0*10)%100 = (0%100 * 10%100)%100 = 0，加1后取模得1。
3. 处理第二位数字2：
   res = (1 * 10 + 2) % 100 = 12
   依据性质：(1*10)%100 = (1%100 * 10%100)%100 = 10，加2后取模得12。
4. 处理第三位数字3：
   res = (12 * 10 + 3) % 100 = 123%100 = 23
   其中(12*10)%100 = (12%100 *10%100)%100 = 120%100 = 20，加3后取模得23。
5. 处理第四位数字4：
   res = (23 * 10 + 4) % 100 = 234%100 = 34
(23*10)%100 = 230%100 = 30，加4后取模得34。
6. 处理第五位数字5：
   res = (34 * 10 + 5) % 100 = 345%100 = 45
   最终结果45，和直接计算12345%100的结果完全一致。

算法有效性的本质 #

我们通过逐位构建原数，每一步都用模运算性质拆解计算，确保中间结果始终不超过模数m（这里是100），避免了超大数字直接计算的溢出问题。每一步的操作(res*10 + digit) %m，本质是组合了两个模运算性质：
(res*10 + digit) %m = [ ((res%m)*(10%m))%m + (digit%m) ]%m
因为之前的res已经是取模后的结果，所以res%m = res，简化后就是算法里的操作逻辑。

内容的提问来源于stack exchange，提问作者aravind ks