模运算法则总结

作者：追风剑情发布于：2018-11-9 15:02 分类：Algorithms

参考 https://baike.baidu.com/item/%E6%A8%A1%E8%BF%90%E7%AE%97/4376110

设: a=k1p+r1 b=k2p+r2 c=k3p+r3

四则运算
(a+b)%p
=(k1p+r1+k2p+r2)%p
=[(k1p+k2p)+(r1+r2)]%p
=(r1+r2)%p
=[(a%p)+(b%p)]%p

(a-b)%p
=(k1p+r1-k2p-r2)%p
=[(k1p-k2p)+(r1-r2)]%p
=(r1-r2)%p
=[(a%p)-(b%p)]%p

(a*b)%p
=[(k1p+r1)*(k2p+r2)]%p
=(k1p*k2p+k1p*r2 + k2p*r1+r1*r2)%p
=[(k1p*k2p+k1p*r2+k2p*r1)+(r1*r2)]%p
=(r1*r2)%p
=[(a%p)*(b%p)]%p

(a%p*b)%p
=(r1*b)%p
=(r1*(k2p+r2))%p
=(r1*k2p+r1*r2)%p
=(r1*r2)%p
=[(a%p)*(b%p)]%p
=(a*b)%p

(a^b)%p
=[(a%p)^b]%p

结合律
((a*b)%p*c)%p=(a*b*c)%p
((a+b)%p+c)%p=(a+(b+c)%p)%p

交换律
(a+b)%p=(b+a)%p
(a*b)%p=(b*a)%p

分配律
((a+b)%p*c)%p
=((r1+r2)%p*c)%p
=((r1+r2)*c)%p
=((r1+r2)*(k3p+r3))%p
=(k3p*r1+r1*r3+k3p*r2+r2*r3)%p
=(r1*r3+r2*r3)%p
=((r1*r3)%p+(r2*r3)%p)%p
=((a*c)%p+(b*c)%p)%p