版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/feilengcui008/article/details/51582198
基本性质
后面两个贼有用
- a≡b(modm)⟺a=k∗m+b
- a≡b(modm)∧c≡d(modm)⟹a+c≡b+d(modm)∧a∗c≡b∗d(modm)
- (a+b)modm=((amodm)+(bmodm))modm
- a∗bmodm=((amodm)∗(bmodm))modm
一些题目的分析与证明
-
大整数的求余与二进制字符串模3余数
证明(直接证明通用x进制的字符串对整数m求余)
假设字符串为A1A2A3...An
则S=A1∗xn−1+A2∗xn−2+...+An为字符串代表的十进制值
Smodm=(A1∗xn−1+A2∗xn−2+...+An)modm
=((A1∗xn−1+A2∗xn−2)modm+(A3∗xn−3...+An)modm)modm
=((A1∗x+A2)∗xn−2modm+(...)modm)modm
=(((A1∗x+A2)modm)∗(xn−2modm)modm+(...)modm)modm
令temp=(A1∗x+A2)modm
=((temp∗(xn−2modm))modm+(...)modm)modm
=(((tempmodm)∗(xn−2modm))modm+(...)modm)modm
=((temp∗xn−2)modm+(...)modm)modm
=(temp∗xn−2+A3∗nn−3+...+An)modm由此我们可以看到递推公式temp=(temp∗x+Anext)modm
二进制字符串模3余数，同上
- 同余幂，求bnmodm，b和m都较大
将n表示成二进制串A1A2…An，则bn=b2A1∗(n−1)+...
用mod的乘法性质和大整数除法类似的证明方法可以得出递推公式
t=(t∗power)modm
power=b2Ai∗(n−i)modm即第i项对m的余数，可以通过幂次递增的递推求得
同余的其他一些应用
- 哈希
- 生成伪随机数(比如线性同余xn=(xn−1∗k+c)modm)
- 加密
