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

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

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

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

　　例如：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是任一整数。因1)的解，则x[0]+k*m'也是(1)的
        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'              ■

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

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