Math 版 (精华区)

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

　　例如：2*x≡3 mod 6
    x≡4 mod 5是这个线性同余式的解。
    定理１　　同余式
                a*x≡b mod m            (1)       
有解的充要条件是d┃b, 其中d=(a,m)。
令m'=m/d。若x[0]是(1)的一个解，则(1)的所有解x 均满足
                x≡x[0] mod m'
　　证明：若x[0]是(1)的一个解，则
                a*x[0]-k*m=b
所以，d=(a,m)除尽b, 即d≡b。
　　反之，若d≡b, 令b=b'*d,
                a=a'*d, m=m'*d
则a'和m'互素，即存在整数p 和q, 使得
                p*a'+q*m=1
从而            b=b*p*a'+b*q*m'
                 =b'*d*p*a'+b'*d*q*m'
                 =p*b'*a+q*b'*m
即p*b'满足同余式(1)。
    不难验证，若x[0]是(1)的解，则x[0]+k*m'也是(1)的
解，其中k是任一整数。因
        a*(x[0]+k*m')=a*x[0]+a*k*m'=a*x[0]+a'*d*k*m'
       =a*x[0]+a'*k*m≡a*x[0]≡b mod m
　　同时，若x[0]'是(1)的任意一个解，可以证明
        x[0]'≡x[0] mod m'
　　若a*x[0]≡b mod m, a*x[0]'≡b mod m, 则
                a*(x[0]=x[0]')≡0 mod m                 
根据定理４，可知
                x[0]≡x[0]' mod m/d
即              x[0]≡x[0]' mod m'              ■
----Page 9              Typed by chan           1998.3.13        
--
        ★来棋牌乐揍揍热闹吧……
        ★http://www.nease.net/~chan (一个住的小屋）
        ★只有天马行空的想象，世界才会变得更理想……
※ 修改:．himen 于 Sep 26 17:01:16 修改本文．[FROM: 159.226.41.166]
--
※ 转寄:．华南网木棉站 bbs.gznet.edu.cn．[FROM: 159.226.41.166]

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