● 计算机密码学之十一 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: hbo (H.B.), 信区: Hacker
标  题: 计算机密码学之十一
发信站: 深大荔园晨风站 (Tue Apr 14 15:47:48 1998), 转信

发信人: chan (Studying...), 信区: Hacker
标  题: 计算机密码学之十一
发信站: 华南网木棉站 (Sat Apr 11 11:08:40 1998), 转信

求y[j]使
        Ｍ[j]*y[j]≡1 mod m[j]    j=1,2,...,k
由于（Ｍ[j],m[j]）=1,所以解y[j]是存在的。令
   x=b[1]*M[1]*y[1]+b[2]*M[2]*y[2]+...+b[k]*M[k]*y[k] (4)
可证明 x 便是(3)式的解.为证明这一点,请注意j≠h时,
m[j]┃M[h]  故
      M[j]≡0 mod m[h]
即 x 中各项险和第 h 项外,其余都模m[h]同余于0 又M[h]*y[h]≡1
mod m[k]
所以  x≡b[h]*M[h]*y[h] mod m[k]
       ≡b[h] mod m[k]
   后面证明(4)式是模m[1]*m[2]*...*m[k]的唯一解.如若不然,设x
   _
和 x是(3)式模M的两个解,即
      _
   x≡x≡b[j] mod m[j]  j=1,2,...,k
        _
那么  x-x≡0 mod m[j]
               _
即    m[j]┃(x-x)
            _
因此  M┃(x-x)
        _
或    x-x≡0 mod M
这就证明了对于模M(3)的解是唯一的.
   定理的证明是构造性的, 它提供了求解的一种步骤.
   例1   求解
      x≡1 mod 2
      x≡2 mod 3
      x≡3 mod 5
      M=2*3*5=30
      M[1]=15,M[2]=10,M[3]=6
      15y[1]≡1 mod 2,y[1]=1
      10y[2]≡1 mod 3,y[2]=1
       6y[3]≡1 mod 5,y[3]=1
----Page 11             Typed by W.Chan

--
※ 来源:．深大荔园晨风站 bbs.szu.edu.cn．[FROM: 202.192.140.143]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店