有关数论算法-中国剩余定理.pptVIP

UniversityofScienceandTechnologyofChinaUniversityofScienceandTechnologyofChinaUniversityofScienceandTechnologyofChinaUniversityofScienceandTechnologyofChinaUniversityofScienceandTechnologyofChina***第十四讲有关数论算法内容提要：初等数论概念最大公约数模运算和模线性方程中国余数定理初等数论概念**素数(质数)：对于整数a1，如果它仅有平凡约数1和a，则a为素数；合数：不是素数的整数a，且a1;整数1被称为基数，它不是素数也不是合数；整数0和所有负整数既不是素数也不是合数；素数和合数整除性和约数d|a，读作”d整除a”，表示a是d的倍数；约数：d|a且d0，则d是a的约数；（即定义约数为非负整数）对整数a最小约数为1，最大为|a|。其中，1和|a|为整数的平凡约数,而a的非平凡约数称为a的因子；初等数论概念**已知一个整数n，所有整数都可以划分为是n的倍数的整数，以及不是n的倍数的整数。对于不是n的倍数的那些整数，又可以根据它们除以n所得的余数来进行分类。——数论的大部分理论都是基于这种划分除法定理（Th31.1）：其中，q为商，值r=amodn称为余数。根据整数模n所得的余数，可以把整数分为n个等价类。包含整数a的模n等价类为：[a]n={a+nk|k∈Z}。如[3]7={…,-4,3,10,17,…}模n等价类可以用其最小非负元素来表示，如3表示[3]7性质：如果a∈[b]n,则a≡b(modn)初等数论概念**初等数论概念**公约数：d是a的约数也是b的约数，则d是a和b的公约数。公约数性质：--d|a且d|b蕴含着d|(a+b)和d|(a-b)--对任意整数x和y，有d|a且d|b蕴含着d|(ax+by)--如果a|b则|a|≤|b|或者b=0,这说明”a|b且b|a，则a=+/-b”最大公约数：--gcd(a,b)表示两个不同时为0的整数a和b的最大公约数；--gcd(a,b)介于1和min(|a|,|b|)之间；gcd基本性质：--gcd(a,0)=|a|;--gcd(a,ka)=|a|;初等数论概念**最大公约数性质：初等数论概念**互质数：如果gcd(a,b)=1,则称a与b为互质数；如果两个整数中每一个数都与一个整数p互为质数，则它们的积与p互为质数，即：唯一因子分解：定理31.7:对所有素数p和所有整数a,b,如果p|ab，则p|a或p|b（或者两者都成立）最大公约数**一种直观求解GCD：根据a和b的素数因子分解，求出正整数a和b的最大公约数gcd(a,b)，即：注：这种解法需要整数的素因子分解，而素因子分解是一个很难的问题（NP问题）最大公约数**欧几里得算法（GCD递归定理）：对任何非负整数a和正整数b，有gcd(a,b)=gcd(b,amodb)；伪代码：Euclid(a,b){ifb=0thenreturna;elsereturnEuclid(b,amodb);}例子：Euclid(30,21)=Euclid(21,9)=Euclid(9,3)=Euclid(3,0)*可以通过证明gcd(a,b)与gcd(b,amodb)能相互整除来证明该定理！P526最大公约数**Euclid算法的运行时间：最大公约数**扩展的Euclid算法：(d,x,y)=(a,1,0)最大公约数**用计算gcd(99,78)的例子说明Extended-Euclid的执行过程:abfloor(a/b)dxy997817821321151156263230-31030131-23-2333-113-1