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

《有关数论算法-中国剩余定理.ppt》由会员分享，可在线阅读，更多相关《有关数论算法-中国剩余定理.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、University of Science and Technology of China2022/12/121第十四讲第十四讲 有关数论算法有关数论算法内容提要：内容提要：p 初等数论概念初等数论概念p 最大公约数最大公约数p 模运算和模线性方程模运算和模线性方程p 中国余数定理中国余数定理University of Science and Technology of China初等数论概念初等数论概念p整除性和约数整除性和约数1）d|a，读作”d整除a”，表示a是d的倍数；2）约数约数：d|a 且d0，则d是a的约数；（即定义约数为非负整数）3）对整数a最小约数为1，最大为|a|。其中，1

2、和|a|为整数的平凡约数,而a的非平凡约数称为a的因子；p素数和合数素数和合数1)素数(质数)：对于整数a 1，如果它仅有平凡约数1和a，则a为素数；2)合数：不是素数的整数a，且 a 1;3)整数1被称为基数，它不是素数也不是合数；4)整数0和所有负整数既不是素数也不是合数；2022/12/122University of Science and Technology of China初等数论概念初等数论概念p已知一个整数n，所有整数都可以划分为是n的倍数的整数，以及不是n的倍数的整数。对于不是n的倍数的那些整数，又可以根据它们除以n所得的余数来进行分类。数论的大部分理论都是基于这种划分p除

3、法定理（除法定理（Th31.1）：）：其中，q为商，值r=a mod n称为余数。p根据整数模n所得的余数，可以把整数分为n个等价类。包含整数a的模n等价类为：an=a+nk|k Z。如 37=,-4,3,10,17,模n等价类可以用其最小非负元素来表示，如3表示37p性质：如果 a bn,则则 a b(mod n)2022/12/123University of Science and Technology of China初等数论概念初等数论概念2022/12/124University of Science and Technology of China初等数论概念初等数论概念p公约数公

4、约数：d是a的约数也是b的约数，则d是a和b的公约数。p公约数性质：公约数性质：-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”p最大公约数：最大公约数：-gcd(a,b)表示两个不同时为0的整数a和b的最大公约数；-gcd(a,b)介于1和min(|a|,|b|)之间；pgcd基本性质：基本性质：-gcd(a,0)=|a|;-gcd(a,ka)=|a|;2022/12/125University of Science and Technolo

5、gy of China初等数论概念初等数论概念p最大公约数性质：最大公约数性质：2022/12/126University of Science and Technology of China初等数论概念初等数论概念p互质数：互质数：如果gcd(a,b)=1,则称a与b为互质数；p如果两个整数中每一个数都与一个整数p互为质数，则它们的积与p互为质数，即：p唯一因子分解：唯一因子分解：2022/12/127定理定理31.7:31.7:对所有素数p和所有整数a,b,如果 p|ab，则 p|a 或 p|b（或者两者都成立）University of Science and Technology of

6、 China最大公约数最大公约数p一种直观求解GCD：根据a和b的素数因子分解，求出正整数a和b的最大公约数gcd(a,b)，即：2022/12/128注：这种解法需要整数的素因子分解，而素因子分解是一个很难的问题（NP问题）University of Science and Technology of China最大公约数最大公约数p欧几里得算法欧几里得算法p（GCDGCD递归定理递归定理）：）：对任何非负整数对任何非负整数a a和正整数和正整数b b，有，有gcd(a,bgcd(a,b)=)=gcd(bgcd(b,a mod b)a mod b)；2022/12/129p伪代码：伪代码：E

7、uclid(aEuclid(a,b),b)if b=0 then if b=0 then return a;return a;else else return return Euclid(bEuclid(b,a mod b);,a mod b);例子：例子：Euclid(30,21)Euclid(30,21)=Euclid(21,9)=Euclid(21,9)=Euclid(9,3)=Euclid(9,3)=Euclid(3,0)=Euclid(3,0)*可以通过证明gcd(a,b)与 gcd(b,a mod b)能相互整除来证明该定理！P526University of Science an

8、d Technology of China最大公约数最大公约数pEuclid算法的运行时间：2022/12/1210University of Science and Technology of China最大公约数最大公约数p扩展的Euclid算法：2022/12/1211University of Science and Technology of China最大公约数最大公约数p用计算gcd(99,78)的例子说明Extended-Euclid的执行过程:2022/12/1212abfloor(a/b)dxy997817821321151156263230-31030131-23-233

9、3-113-1114(d,x,y)=(a,1,0)University of Science and Technology of China模运算和模线性方程模运算和模线性方程p群(S,)是一个集合S和定义在S上的二进制运算，且满足封闭性、单位元、结合律、逆元等4个性质；p交换群（a b=b a）和有限群：2022/12/1213University of Science and Technology of China14n其中，其中，p p包括能整除包括能整除n n的所有素数（如果的所有素数（如果n n是素数，则也包括是素数，则也包括n n本身）本身）n直观上看，开始时有一张直观上看，开始时

10、有一张n n个余数组成的表个余数组成的表0,1,n-10,1,n-1，然后对每，然后对每个能整除个能整除n n的素数的素数p p，在表中划掉所有是，在表中划掉所有是p p的倍数的数。的倍数的数。n如果如果p p是素数，则是素数，则ZpZp*=1,2,p-1,*=1,2,p-1,并且并且(p(p)=p-1)=p-1n如果如果n n是合数，则是合数，则(n(n)n-1)n-1模运算和模线性方程模运算和模线性方程University of Science and Technology of China15模运算和模线性方程模运算和模线性方程p子群：如果(S,)是一个群，S是S的一个子集，并且（S,)

11、也是一个群，则(S,)称为(S,)的子群。p 下面定理对子群规模作出了一个非常有用的限制：University of Science and Technology of China模运算和模线性方程模运算和模线性方程2022/12/1216p 由一个元素生成的子群：从有限群(S,)中，选取一个元素a，并取出根据群上的运算由a所能生成的所有元素，这些元素构成了原有限群的一个子群。*在群 Zn 中，有a(k)=ka mod n；*在群 中，有a(k)=ak mod n；p 由a生成的子群用或者(,)来表示，其定义如下：=a(k):k 1 称为 a 生成子群或者a是的生成元。University o

12、f Science and Technology of China17l问题描述：问题描述：模运算和模线性方程模运算和模线性方程University of Science and Technology of China18p群表示和构造定理模运算和模线性方程模运算和模线性方程University of Science and Technology of China模运算和模线性方程模运算和模线性方程p推论推论1 1：方程ax b(mod n)对于未知量x有解，当且仅当 gcd(a,n)|b。p推论推论2 2：方程ax b(mod n)或者对模n有d个不同的解，其中 d=gcd(a,n)，或者无

13、解。2022/12/1219University of Science and Technology of China20模运算和模线性方程模运算和模线性方程University of Science and Technology of China21p输入输入a a和和n n为任意正整数，为任意正整数，b 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 e

14、lse print“no solutions”模运算和模线性方程模运算和模线性方程University of Science and Technology of China22求解方法：模运算和模线性方程模运算和模线性方程University of Science and Technology of China模运算和模线性方程模运算和模线性方程2022/12/1223University of Science and Technology of China中国余数定理中国余数定理p中国余数定理，也称中国剩余定理，孙子剩余定理。中国余数定理，也称中国剩余定理，孙子剩余定理。p从从孙子算经孙子算

15、经到秦九韶到秦九韶数书九章数书九章对一次同余式问题的研究对一次同余式问题的研究成果，在世纪中期开始受到西方数学界的重视。年，成果，在世纪中期开始受到西方数学界的重视。年，英国传教士伟烈亚力向欧洲介绍了英国传教士伟烈亚力向欧洲介绍了 孙子算经孙子算经的的“物不知数物不知数”题和秦九韶的题和秦九韶的“大衍求一术大衍求一术”；年，德国人马蒂生指出，；年，德国人马蒂生指出，中国的这一解法与西方世纪高斯中国的这一解法与西方世纪高斯算术探究算术探究中关于一次同中关于一次同余式余式 组的解法完全一致。从此，中国古代数学的这一创造逐渐受组的解法完全一致。从此，中国古代数学的这一创造逐渐受到世界学者的瞩目，并在

16、西方数学史著作中正式被称为到世界学者的瞩目，并在西方数学史著作中正式被称为“中国剩中国剩余定理余定理”。2022/12/1224University of Science and Technology of China中国余数定理中国余数定理p韩信点兵：韩信点兵：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，立了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让为了保住军事机密，不让 敌人知道自己部队的实力，先令士兵从敌人知道自己

17、部队的实力，先令士兵从1 1至至3 3报报数，然后记下最后一个士兵所报之数；再令士兵从至报数，也记下数，然后记下最后一个士兵所报之数；再令士兵从至报数，也记下最后一个士兵所报之数；最后令士兵从最后一个士兵所报之数；最后令士兵从1 1至至7 7 报数，又记下最后一个士兵报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。终无法弄清他的部队究竟有多少名士兵。2022/12/1225 这个故事中所说的韩信点兵的计算方法，就是现在被称为这个故事中所说的韩信点兵的计算方法，

18、就是现在被称为“中国剩余定理中国剩余定理”的一的一次同余式解法。它是中国古代数学家的一项重大创造，在世界数学史上具有重要的次同余式解法。它是中国古代数学家的一项重大创造，在世界数学史上具有重要的地位。地位。University of Science and Technology of China中国余数定理中国余数定理2022/12/1226p 最早提出并记叙这个数学问题的，是南北朝时期的数学著作最早提出并记叙这个数学问题的，是南北朝时期的数学著作孙子算经孙子算经中的中的“物不知数物不知数”题目。这道题目。这道“物不知数物不知数”的题目是这样的的题目是这样的：“今有一些物不知其数量。如果三个三

19、个地去数它，则最后还剩二个；如今有一些物不知其数量。如果三个三个地去数它，则最后还剩二个；如果五个五个地去数它，则最后还剩三个；如果七个七个地去数它，则最后果五个五个地去数它，则最后还剩三个；如果七个七个地去数它，则最后也剩二个。问：这些物一共有多少？也剩二个。问：这些物一共有多少？”p 用数学语言来表述就是如下线性同余方程用数学语言来表述就是如下线性同余方程 孙子算经孙子算经实际上是给出了这类一次同余式组实际上是给出了这类一次同余式组 的一般解：的一般解：University of Science and Technology of China中国余数定理中国余数定理2022/12/1227

20、p 但由于题目比较简单，甚至用试猜的方法也能求得，所以但由于题目比较简单，甚至用试猜的方法也能求得，所以孙子孙子算经算经尚没有上升到一套完整的计算程序和理论的高度。尚没有上升到一套完整的计算程序和理论的高度。p 真正从完整的计算程序和理论上解决这个问题的，是南宋时期的真正从完整的计算程序和理论上解决这个问题的，是南宋时期的数学家数学家秦九韶秦九韶。秦九韶在他的。秦九韶在他的数书九章数书九章中提出了一个数学方法中提出了一个数学方法“大衍求一术大衍求一术”，系统地论述了一次同余式组解法的基本原理和一，系统地论述了一次同余式组解法的基本原理和一般程序。般程序。p 如今，中国余数定理广泛应用于通信领域

21、。譬如，电子工程师如今，中国余数定理广泛应用于通信领域。譬如，电子工程师发明的发明的“中国余数码中国余数码”(Chinese Remainder Code)(Chinese Remainder Code)是一种常用的是一种常用的纠错编码纠错编码 (error correcting code)(error correcting code)。University of Science and Technology of China中国余数定理中国余数定理p定理定理31.24:31.24:假设方程 ax b(mod n)有解（即有gcd(a,n)|b）,x0是方程的任意一个解，则该方程对模n恰有d个

22、不同的解，分别为：xi=x0+i(n/d)(i=1,2,d-1)p推论推论31.2531.25：对任意n 1,如果gcd(a,n)=1，则方程 ax b(mod n)对模n有唯一解。p推论推论31.2631.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；2022/12/1228University of Science and Technology of China中国余数定理中国余数定理pa 模n的逆存在唯一性定理:2022/12/1229University of Science and Technology of China中国余数定理中国余数定理2022/12/1230University of Science and Technology of China谢谢！谢谢！2022/12/1231Q&A作业：作业：31.1-12 31.2-4 31.3-5 31.4-3