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

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

发信人: hbo (H.B.), 信区: Hacker
标  题: 计算机密码学之十(转寄)
发信站: 深大荔园晨风站 (Mon Mar 30 11:03:16 1998), 转信

发信人: chan (Hacking...), 信区: Hacker
标  题: 计算机密码学之十
发信站: 华南网木棉站 (Mon Mar 30 09:49:14 1998), 转信

§５　联立的同余式和中国剩余定理
　　定理１　下列两个同余式
        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]

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

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