Math 版 (精华区)

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

证明：因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
的同余解。
----Page 8              Typed by chan                   1998.3.13    
--
        ★来棋牌乐揍揍热闹吧……
        ★http://www.nease.net/~chan (一个住的小屋）
        ★只有天马行空的想象，世界才会变得更理想……
※ 修改:．himen 于 Sep 26 17:01:09 修改本文．[FROM: 159.226.41.166]
--
※ 转寄:．华南网木棉站 bbs.gznet.edu.cn．[FROM: 159.226.41.166]

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