● 计算机密码学之十四 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

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

发信人: hbo (H.B.), 信区: Hacker
标  题: 计算机密码学之十四
发信站: 深大荔园晨风站 (Tue Apr 14 15:50:50 1998), 转信

发信人: chan (Studying...), 信区: Hacker
标  题: 计算机密码学之十四
发信站: 华南网木棉站 (Sat Apr 11 11:12:53 1998), 转信

    0<=x<│m[1]*m[2]│
设      x≡r[1] mod m[1], x≡r[2] mod m[2]
其中    0<=r[1]<m[1],0<=r[2]<m[2]
则r[1],r[2]为x所唯一确定.
    反之,给定r[1],r[2]可唯一确定x, 即x和一对数偶(r[1],r[2])
一一对应.x和m[1]*m[2]互素,当且仅当x 分别和m[1],m[2]都互素,
同时 x和m[i]互素的充要条件是r[i]和m[i]互素,i=1,2.
    这就证明了与m[1]*m[2]互素的 x 数目等于数偶(r[1],r[2])的
数目,其中r[1]和m[1]第素, r[2]和m[2]互素. 比m[1]小而 m[1]经互素
的r[1]的数目为Φ(m[1]),小于m[2]而与m[2]互素的r[2]的数目为Φ(m[2]),
这样的数偶(r[1],r[2])的数目为Φ(m[1])*Φ(m[2]).
                 k
    定理2   若m= Π (p[i]^a[i]), 则
                 i=1
                 k
        Φ(m)=m* Π (1-1/p[i])
                 i=1
    证明:首先证明对于素数 p有
        Φ(p^a)=p^a*(1-1/p)
    在区间0<=x<p^a上的整数,或是p的倍数,或与p^a互素，
其中p的倍数为
            0,p,2*p,...,(p^(a-1)-1)*p
共为p^(a-1)个.所以和p^a互素的数目为
            p^a-p^(a-1)=p^a * (1-1/p)
根据定理1 得
           k
    Φ(m)= Π (p[i]^a[i]*(1-1/p[i]))
           i=1
              k
         = m* Π (1-1/p[i])
              i=1
    (2) Euler 定理
    定理3 若a和m互素, 则
----Page 14

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

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