算法描述
如果对于任意0<=a<p和0<=b<q(p和q皆是素数),那么当x<p*q时,存在一个唯一的x,使得x≡a mod p 且 x≡b mod q,则
x =(((a - b)*u) mod p)*q + b,其中u满足u*q≡1 mod p。
算法证明
1.先推导x的解
因x≡a mod p 且 x≡b mod q
故令x = k1*p + a 且 x = k2*q + b (1)
即 k1*p + a = k2*q + b
=> a - b = k2*q - k1*p (2)
又因u*q≡1 mod p,故令u*q = 1 + k3*p (3)
由(2)和(3)式
=> a - b = k2 * (1+k3*p)/u - k1*p
两边同时乘u
=>(a - b) * u = k2*(1+k3*p) - k1*p*u
两边同时模p
=> ((a - b) * u) mod p = (k2 mod p) mod p (4)
又因x < p*q,故b + k2*q < p*q
=> b <(p - k2) * q
因0<b<q,故p > k2
=> (k2 mod p) mod p = k2
故(4)式即
((a - b) * u) mod p = k2 (5)
将(5)代入(1)式可得
x = (((a - b)*u) mod p)*q + b
2. 再证明x是唯一解
假设x1是另一解,即 x1≡a mod p 且 x1≡b mod q,得
x1 - x ≡ 0 mod p 即 p | x1 - x
x1 - x ≡ 0 mod q 即 q | x1 - x
又因p和q皆为素数,故p*q | x1 - x,得
x1 - x ≡ 0 mod (p*q)
故 x1 mod (p*q) = x mod (p*q) 证毕
posted on 2021-09-19 16:01
春秋十二月 阅读(1003)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm