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

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

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

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

依次消去r[k-1],r[k-2],...,r, 可得
        d=r[k]=p*a+q*b
由上例１可知
        3=27-4x6
         =27-4x(33-27)
          =-4x33_5x27
          =-4x33+5x(60-33)
          =5x60-9x33
          =5x60-9x(333-5x60)
          =-9x333+50x60
          =-9x333+50x(393-333)
          =50x393-59x333
          =50x393-59x(726-393)
          =-59x726+109x393
        若gcd{a,b}=±1, 则称a和b互素。１和任意整数互素。
        若a和b互素，则根据定理３，存在整数p和q, 便得
                p*a+q*b=1
　　定理４　若a┃b*c, gcd{a,b}=1, 那么a┃c。
　　证明：若a和b互素，则将p*a+q*b=1的两端同乖以c，得
                p*a*c+q*b*c=c
由假定，a┃×，所以a 除尽等式的左端，因此a┃c。
　　推论　若素数ｐ除尽a[1]*a[2]*...*a[n], 则必存在k: １<=k<=n, 使得
p┃a[k]。
p┃a[3]...a[n]; ......。，则p┃a[2]...a[n]; 若p 也和a[2]互素，则
　　若p和a[1],a[2],...,a[n-1]的每一个互素，则最后有p┃a[n]。■
　　定理５　每一个正合数，可表示为正素数的乖积，并且不考
虑乖积的顺序时，表示法是唯一的。
　　证明：若c 是合数，则存在a 和b, 合得c=a*b; 若a 和b 是合

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

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