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

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理