Math 版 (精华区)

发信人: flytigger (Ostrich), 信区: Math
标  题: 计算机密码学之十
发信站: 哈工大紫丁香 (Sun Sep 26 17:44:34 1999), 转信

§５　联立的同余式和中国剩余定理
　　定理１　下列两个同余式
        x≡b[1] mod m[1], x≡b[2] mod m[2]      (1)
有一个其同解的充要条件是
        b[1]≡b[2] mod d, d=(m[1],m[2])
　　证明：设x[1]满足(1)的两个同余式，则
        x[1]=b[1]+k[1]*m[1]=b[2]+k[2]*m[2]
从而　　k[2]*m[2]≡b[1]-b[2] mod m              (2)
从§４定理１可知，(2)式中k[2]存在的充要条件是
        (m[1],m[2])┃(b[1]-b[2])                          
　　对于n 个联立同余式同样有类似结果
　　定理２　对于联立同余式
        x≡b[i] mod m[i]     i=1,2,...,n
有一共同的解的充要条件是
        (m[i],m[j])┃(b[i]-b[j]),i≠j,i,j=1,2,...,n
　　证明从略。
　　定理３　若a≡b mod m[1],a≡b mod m[2],...,a≡b mod m[k]
则
        a≡b mod lcm{m[1],m[2],...,m[k]}
　　证明：因a≡b mod m[i], i=1,2,...,k
        lcm{m[1],m[2],...,m[k]}┃(a=b)
从而    a≡b mod lcm{m[1],m[2],...,m[k]}
　　中国剩余定理　设m[1],m[2],...,m[k]是两两互素的正整数，则
        x≡b[i] mod m[i], i=1,2,...,k           (3)
模lcm{m[1],m[2],...,m[k]}有唯一解。
　　证明：令Ｍ=m[1]*m[2]*...*m[k]
      Ｍ[j]=Ｍ/m[j]=m[1]*m[2]*...*m[j-1]*m[j+1]*...*m[k]
----Page 10     Typed by chan           1998.3.13               

--
        ★来棋牌乐揍揍热闹吧……
        ★http://www.nease.net/~chan (一个住的小屋）
        ★只有天马行空的想象，世界才会变得更理想……
※ 修改:．himen 于 Sep 26 17:48:21 修改本文．[FROM: 159.226.41.166]
--
※ 转寄:．华南网木棉站 bbs.gznet.edu.cn．[FROM: 159.226.41.166]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: himen.bbs@melon.gzne]