算法导论-ch31 Number-Theoretic Algorithms.pdf

数数数数数数数数论论论论论论论论 算算算算算算算算法法法法法法法法 NumberNumber-NumberNumber--Theoretic Algorithms-Theoretic AlgorithmsTheoretic AlgorithmsTheoretic Algorithms 主讲人主讲人主讲人主讲人 徐徐徐徐 云云云云 FallFall 2012,2012, USTCUSTC 数论算法数论算法 （（Ch31Ch31）） 11 初等数论记号初等数论记号 （（31.131.1）） 2222 最大公约数最大公约数最大公约数最大公约数 （（（.2222）））） 33 模运算模运算 （（31.331.3）） 44 求解线性模方程求解线性模方程 （（31.431.4）） 5555 中国余数定理中国余数定理中国余数定理中国余数定理（（（.5555）））） 6 RSA6 RSA公钥密码系统公钥密码系统 （（31.731.7）） 77 素数判定素数判定 （（31.831.8）） 初等数论记号初等数论记号 （（31.131.1））  算术计算中的输入规模和成本算术计算中的输入规模和成本  除定理除定理除定理除定理  公约数和最大公约数公约数和最大公约数  互素数和最大公约数互素数和最大公约数 算术计算中的输入规模和成本  Def.1 一个输个输入整入整数数aa ,aa ,…,aa 的算法是多的算法是多项项式式时间时间算法算法，如果其如果其 11 22 kk 运行时间是以loga ,loga ,…,loga 为多项式时间的，即以输入 1 2 k 参数二进制编码长度的多项式时间的。 2  如如，两个两个ββ位的整位的整数数乘法乘法，普通乘法使用普通乘法使用θθ((ββ )), log3 改进的算法使用θ(β )，甚至θ(βlogβloglogβ) 2012/10/31 4 除定理 概念：可除性，素数，合数 Th31.1 对对任何整任何整数数a和正整和正整数数n，存在唯存在唯一整整数数q和和r，使得使得 a=qn+r，这里q= a/n，0≤ r ＜n。 注: q为商，r为余数  Def. 2 模n的等价类类: [[a]] ={{ a+kn || k ∈Z}} nn - 性质: 如果如果aa ∈∈[b][b] ，则则aa≡≡b ( mod n)b ( mod n) n 2012/10/31 5 除定理  Spiral Visualization of mod: Example shown: ≡ 0 (mod 5) 20