算法描述
如果对于任意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
春秋十二月 阅读(1012)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm