数论算法ch31

《数论算法ch31》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数数数论算法论论算算法法NumberNumberNumber-TheoreticAlgorithms--TheoreticAlgorithmsTheoreticAlgorithms主讲人主讲人徐徐云云Fall2010,USTC数论算法数论算法（（Ch31Ch31））11初等数论记号初等数论记号（（31.1））22最大公约数最大公约数（（31.2））33模运算模运算（（31.3））44求解线性模方程求解线性模方程（（31.4））55中国余数定理中国余数定理（（31.5））6RSA6RSA公钥密码系统公钥密码系统（（3

2、1.7））77素数判定素数判定（（31.8））初等数论记号初等数论记号（（31.131.1））¢算术计算中的输入规模和成本算术计算中的输入规模和成本¢除定理除定理¢公约数和最大公约数公约数和最大公约数¢互素数和最大公约数互素数和最大公约数算术计算中的输入规模和成本¢Def.1一个输入整数a,a,…,a的算法是多项式时间算法，如果其12k运行时间是以loga,loga,…,loga为多项式时间的，即以输入12k参数二进制编码长度的多项式时间的。2¢如，两个β位的整数乘法，普通乘法使用θ(β),改进的算法使用θ(βlo

3、g3)，甚至θ(βlogβloglogβ)2010-11-14除定理¢概念：可除性，素数，合数¢Th31.1对任何整数a和正整数n，存在唯一整数q和r，使得a=qn+r，这里q=⎣a/n⎦，0≤r＜n。注:q为商，r为余数¢Def.2模n的等价类:[a]={a+kn

4、k∈Z}n-性质:如果a∈[b]，则a≡b(modn)n2010-11-15除定理¢SpiralVisualizationofmod:≡0Exampleshown:(mod5)20modulo-5arithmetic15≡110(mod5)≡41952

5、11416(mod5)9401161328713121817≡322≡2(mod5)(mod5)2010-11-16公约数和最大公约数¢概念：约数，公约数，最大公约数¢Th31.2a，b为不全为零的两个整数，则最大公约数gcd(a,b)是{ax+by

6、x,y∈Z}中最小的正整数。-系1:对所有整数a和b，如果d

7、a，d

8、b，则d

9、gcd(a,b)-系2:对所有整数a和b，和非负整数n，有gcd(an,bn)=ngcd(a,b)-系3:对所有正整数n、a和b，如果n

10、ab且gcd(a,n)=1，则n

11、b2010-11

12、-17互素数和素数唯一性分解定理¢Def.3：如果gcd(a,b)=1，称整数a和b为互素数¢Th31.6∀a,b,p∈Z，如果gcd(a,p)=1和gcd(b,p)=1，则gcd(ab,p)=1¢Th31.8(唯一分解定理)一个合数a能被唯一写成形式a=pe1pe2…per12r这里p是素数，p

13、算模运算（（31.3））44求解线性模方程求解线性模方程（（31.4））55中国余数定理中国余数定理（（31.5））6RSA6RSA公钥密码系统公钥密码系统（（31.7））77素数判定素数判定（（31.8））最大公约数最大公约数（（31.231.2））¢一种直观的解一种直观的解GCDGCD¢EuclidEuclid’’ssAlgriothmAlgriothm¢EuclidEuclid’’ssAlgriothmAlgriothm的运行时间的运行时间¢扩展的扩展的EuclidEuclid’’ssAlgriothmAlg

14、riothm一种直观解GCDa=pe1pe2…per和b=pf1pf2…pfr12r12r⇒gcd(a,b)=pmin(e1,f1)pmin(e2,f2)…pmin(er,fr)12r注:这种解法需要整数的素因子分解，而素因子分解是一个很难的问题(NP问题)2010-11-111Euclid’sAlgorithm¢Th.31.9(GCDRecursion)对任何非负整数a和正整数b，有gcd(a,b)=gcd(b,amodb)¢Euclid’sAlgorithmEuclid(a,b){ifb=0thenreturn

15、a;elsereturnEuclid(b,amodb);}¢例:gcd(30,21)2010-11-112Euclid’sAlgorithm的运行时间¢Th.31.11(拉姆定理)对整数k≥1，如果a>b≥1且b