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

《有关数论算法-中国剩余定理.ppt》由会员分享，可在线阅读，更多相关《有关数论算法-中国剩余定理.ppt（31页珍藏版）》请在三一办公上搜索。

1、2023/8/16,1,第十四讲 有关数论算法,内容提要：初等数论概念 最大公约数 模运算和模线性方程 中国余数定理,初等数论概念,整除性和约数1）d|a，读作”d整除a”，表示a是d的倍数；2）约数：d|a 且d0，则d是a的约数；（即定义约数为非负整数）3）对整数a最小约数为1，最大为|a|。其中，1和|a|为整数的平凡约数,而a的非平凡约数称为a的因子；素数和合数1)素数(质数)：对于整数a 1，如果它仅有平凡约数1和a，则a为素数；2)合数：不是素数的整数a，且 a 1;3)整数1被称为基数，它不是素数也不是合数；4)整数0和所有负整数既不是素数也不是合数；,2023/8/16,2,初

2、等数论概念,已知一个整数n，所有整数都可以划分为是n的倍数的整数，以及不是n的倍数的整数。对于不是n的倍数的那些整数，又可以根据它们除以n所得的余数来进行分类。数论的大部分理论都是基于这种划分除法定理（Th31.1）：其中，q为商，值r=a mod n称为余数。根据整数模n所得的余数，可以把整数分为n个等价类。包含整数a的模n等价类为：an=a+nk|k Z。如 37=,-4,3,10,17,模n等价类可以用其最小非负元素来表示，如3表示37性质：如果 a bn,则 a b(mod n),2023/8/16,3,初等数论概念,2023/8/16,4,初等数论概念,公约数：d是a的约数也是b的约

3、数，则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|;,2023/8/16,5,初等数论概念,最大公约数性质：,2023/8/16,6,初等数论概念,互质数：如果gcd(a,b)=1,则称a与b为互质数；如果两个

4、整数中每一个数都与一个整数p互为质数，则它们的积与p互为质数，即：唯一因子分解：,2023/8/16,7,定理31.7:对所有素数p和所有整数a,b,如果 p|ab，则 p|a 或 p|b（或者两者都成立）,最大公约数,一种直观求解GCD：根据a和b的素数因子分解，求出正整数a和b的最大公约数gcd(a,b)，即：,2023/8/16,8,注：这种解法需要整数的素因子分解，而素因子分解是一个很难的问题（NP问题）,最大公约数,欧几里得算法（GCD递归定理）：对任何非负整数a和正整数b，有gcd(a,b)=gcd(b,a mod b)；,2023/8/16,9,伪代码：Euclid(a,b)if

5、 b=0 then return a;else return Euclid(b,a mod b);,例子：Euclid(30,21)=Euclid(21,9)=Euclid(9,3)=Euclid(3,0),*可以通过证明gcd(a,b)与 gcd(b,a mod b)能相互整除来证明该定理！P526,最大公约数,Euclid算法的运行时间：,2023/8/16,10,最大公约数,扩展的Euclid算法：,2023/8/16,11,最大公约数,用计算gcd(99,78)的例子说明Extended-Euclid的执行过程:,2023/8/16,12,模运算和模线性方程,群(S,)是一个集合S和定

6、义在S上的二进制运算，且满足封闭性、单位元、结合律、逆元等4个性质；交换群（a b=b a）和有限群：,2023/8/16,13,14,其中，p包括能整除n的所有素数（如果n是素数，则也包括n本身）直观上看，开始时有一张n个余数组成的表0,1,n-1，然后对每个能整除n的素数p，在表中划掉所有是p的倍数的数。如果p是素数，则Zp*=1,2,p-1,并且(p)=p-1如果n是合数，则(n)n-1,模运算和模线性方程,15,模运算和模线性方程,子群：如果(S,)是一个群，S是S的一个子集，并且（S,)也是一个群，则(S,)称为(S,)的子群。,下面定理对子群规模作出了一个非常有用的限制：,模运算和

7、模线性方程,2023/8/16,16,由一个元素生成的子群：,从有限群(S,)中，选取一个元素a，并取出根据群上的运算由a所能生成的所有元素，这些元素构成了原有限群的一个子群。,*在群 Zn 中，有a(k)=ka mod n；*在群 中，有a(k)=ak mod n；,由a生成的子群用或者(,)来表示，其定义如下：=a(k):k 1 称为 a 生成子群或者a是的生成元。,17,问题描述：,模运算和模线性方程,18,群表示和构造定理,模运算和模线性方程,模运算和模线性方程,推论1：方程ax b(mod n)对于未知量x有解，当且仅当 gcd(a,n)|b。推论2：方程ax b(mod n)或者对

8、模n有d个不同的解，其中 d=gcd(a,n)，或者无解。,2023/8/16,19,20,模运算和模线性方程,21,输入a和n为任意正整数，b为任意整数Modular-Linear-Equation-Solver(a,b,n)（d,x,y)Extended-Euclid(a,n);if d|b then x0 x(b/d)mod n for i 0 to d-1 do printf(x0+i(n/d)mod n else print“no solutions”,模运算和模线性方程,22,求解方法：,模运算和模线性方程,模运算和模线性方程,2023/8/16,23,中国余数定理,中国余数定理，

9、也称中国剩余定理，孙子剩余定理。从孙子算经到秦九韶数书九章对一次同余式问题的研究成果，在世纪中期开始受到西方数学界的重视。年，英国传教士伟烈亚力向欧洲介绍了 孙子算经的“物不知数”题和秦九韶的“大衍求一术”；年，德国人马蒂生指出，中国的这一解法与西方世纪高斯算术探究中关于一次同余式 组的解法完全一致。从此，中国古代数学的这一创造逐渐受到世界学者的瞩目，并在西方数学史著作中正式被称为“中国剩余定理”。,2023/8/16,24,中国余数定理,韩信点兵：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让

10、敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从至报数，也记下最后一个士兵所报之数；最后令士兵从1至7 报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。,2023/8/16,25,这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的一次同余式解法。它是中国古代数学家的一项重大创造，在世界数学史上具有重要的地位。,中国余数定理,2023/8/16,26,最早提出并记叙这个数学问题的，是南北朝时期的数学著作孙子算经中的“物不知数”题目。这道“物不知数”的题目是这样的：,“

11、今有一些物不知其数量。如果三个三个地去数它，则最后还剩二个；如果五个五个地去数它，则最后还剩三个；如果七个七个地去数它，则最后也剩二个。问：这些物一共有多少？”,用数学语言来表述就是如下线性同余方程,孙子算经实际上是给出了这类一次同余式组 的一般解：,中国余数定理,2023/8/16,27,但由于题目比较简单，甚至用试猜的方法也能求得，所以孙子算经尚没有上升到一套完整的计算程序和理论的高度。真正从完整的计算程序和理论上解决这个问题的，是南宋时期的数学家秦九韶。秦九韶在他的数书九章中提出了一个数学方法“大衍求一术”，系统地论述了一次同余式组解法的基本原理和一般程序。,如今，中国余数定理广泛应用于

12、通信领域。譬如，电子工程师发明的“中国余数码”(Chinese Remainder Code)是一种常用的纠错编码(error correcting code)。,中国余数定理,定理31.24:假设方程 ax b(mod n)有解（即有gcd(a,n)|b）,x0是方程的任意一个解，则该方程对模n恰有d个不同的解，分别为：xi=x0+i(n/d)(i=1,2,d-1)推论31.25：对任意n 1,如果gcd(a,n)=1，则方程 ax b(mod n)对模n有唯一解。推论31.26：对任意n 1,如果gcd(a,n)=1，则方程 ax 1(mod n)对模n有唯一解，否则无解。所求得的解x是a对模n乘法的逆元，并用记号(a-1 mod n)来表示；如果gcd(a,n)=1，则方程ax 1(mod n)的一个解就是EXTENDED-EUCLID所返回的整数x；,2023/8/16,28,中国余数定理,a 模n的逆存在唯一性定理:,2023/8/16,29,中国余数定理,2023/8/16,30,谢谢！,2023/8/16,31,Q&A作业：31.1-12 31.2-4 31.3-5 31.4-3,