算法描述
如果對于任意0<=a<p和0<=b<q(p和q皆是素數(shù))，那么當(dāng)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.先推導(dǎo)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是唯一解
假設(shè)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皆為素數(shù)，故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
春秋十二月 閱讀(1041)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm