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

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

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

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

证明：因a≡b mod m, c≡d mod m, 所以

                a=k*m+b, c=h*m+d
                a±c=(k±h)*m+(b±d)
从而            a±c≡b±d mod m
    同理可证：a*c±b*d mod m。
    定理３　若a*c≡b*c mod m, 且c 和m 互素，则
                a≡b mod m。
    证明：由a*c≡b*c mod m, 可知
                a*c=k*m+b*c
即              c(a-b)=k*m
由于c 和m 互素，因此c┃k。设k=h*c, 则
                c(a-b)=h*c*m
        a-b=h*m或a≡b mod m
　　定理４　若a*c≡b*c(mod m), d=(c,m), 则
                a≡b mod m/d。
    例：因42≡7 mod 5, (7,5)=1, 所以
                6≡1 mod 5
§４　线性同余式
　　若整数x[1]满足线性同余式
                a*x≡b mod m
即              a*x[1]≡b mod m
可证明模m 与x[1]同余的所有整数都满足这个线性同余式，即若
x[2]≡x[1] mod m,　则
                a*x[2]≡b mod m
模m 和x[1]同余的整数构成同余式
                a*x≡b mod m
的同余解。

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

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