cnspp-ch08-introduction to number theory

《cnspp-ch08-introduction to number theory》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章数论入门素数是一种整数，在整除意义下，它只能被自身(正负)和1整除。素数在数论和密码学里扮演重要角色。在公钥密码里起重要作用的定理是费马小定理欧拉定理中国剩余定理。许多密码算法的一个重要前提是能够选择一个大的素数。开发有效素检测算法判定一个随机整数是否为素数是密码研究重要课题。离散对数是许多公钥算法的基础。离散对数和普通对数类似，但是在模算术上进行运算。素数整数p>1是素数当且仅当它只有因子±1和±p。0，1都不是素数2是最小的素数，也是唯一的偶素数如2,3,5,7是素数,4,6,8,9,10不是素数是数论的核心整数的素因子分解分

2、解是指将任何整数n>1,分解为其他整数乘积的形式，即n=a×b×…×c比起用乘的方法把几个因子乘起来生成合数,分解合数通常要困难得多。任何整数a>1,都可以唯一分解为a=p1a1p2a2…ptat,其中,p1

3、,a3=2},91可以表示为{a7=1,a13=1}两个数的乘法等同于对应指数分量的加法。k=12×18=(22×3)×(2×32)=216,k2=2+1=3,k3=1+2=3,∴216=23×33={a2=3,a3=3}任何以pk形式表示的整数仅能被对应素数分量小于或等于它的另一个整数pj整除,其中j≤k,因此有a

4、b→ap≤bp对所有p.a=12,b=36,12

5、36,12=22×31,36=22×32，a2=2=b2,a3=1≤2=b3求解最大公因子GCDgcd(a,b)=k,即k是a和b的最大公约数,当k是a和b的因子任何a和b的因

6、子也是k的因子下列关系总是成立的如果k=gcd(a,b),则kp=min(ap,bp),对于任意的p∊P如果将整数表示为素数之积,则容易确定两个正整数的最大公因子300=22×31×52,18=21×32,gcd(18,300)=21×31×50=6确定一个大数的素因子不是一件容易的事费马小定理定理(费马小定理)若p是素数,a是正整数且不能被p整除,则ap-1modp=1证明：考虑小于p的正整数集合{1,2,...,(p-1)}(即Zp*)a乘以Zp*中所有元素并对p取模得{amodp,2amodp,...,(p-1)amodp},是Zp*

7、的一个置换p-1个数amodp,2amodp,...,(p-1)amodp互不相等p-1个数amodp,2amodp,...,(p-1)amodp的取值范围为p-1个数的集合{1,2,...,(p-1)}置换的两个集合中各元素分别相乘应相等。a×2a×...×(p-1)a=(p-1)!ap-1modp≡(p-1)!modp(p-1)!与p互素,由引理1即得ap-1modp=1.引理1.若a,b,c为任意3个整数，m为正整数，且(m,c)=1,则当ac≡bc(modm)时，有a≡b(modm)证明ac≡bc(modm)=>ac–bc≡0(mo

8、dm)=>(a-b)c≡0(modm)因为(m,c)=1即m,c互素，c可以约去(a-b)c≡0(modm),即m

9、(a-b)c,又因为m,c互素,所以m

10、(a-b),即(a-b)≡0(modm)=>a–b≡0(modm)=>a≡b(modm)费马小定理的等价形式费马小定理等价形式ap≡amodp,p是素数费马小定理前一种形式要求a，p互素。等价形式则没有要求。剩余类集/完全剩余类集/缩剩余类集定义比n小的非负整数集合Zn，Zn={0,1,…,(n-1)}为剩余类集。Zn中每一个整数都代表着一个剩余类。模n的完全剩余类集：如果对每个整数a，

11、在集合{r1,r2,…,rn}中恰有一个余数ri，使得a=rimodn,则称{r1,r2,…,rn}为模n的完全剩余集。Zn形成模n的完全剩余类集。模n的缩剩余类集：完全剩余集的一个子集，指的是集合中的元素都和n互素，记为Zn*Z10={0,1,2,3,4,5,6,7,8,9};Z10*={1,3,7,9}欧拉函数φ(n)φ(n)是比n小且与n互素的正整数的个数，即模n的缩剩余系中元素之个数。计算ø(n)需要计算与n不互素的元素的个数例如ø(37)=36ø(14)=#{1,3,5,9,11,13}=6对素数p，ø(p)=p-1对n=pq(p

12、,q是素数)ø(n)=(p-1)(q-1)例如ø(14)=(2–1)×(7–1)=1×6=6欧拉函数φ(n)欧拉函数φ(n)定理：p和q是素数,n=p*q,φ(n)=φ(p)φ(