第十四讲 有关数论算法 内容提要： 初等数论概念 最大公约数 模运算和模线性方程 中国余数定理 2019/4/24

初等数论概念 整除性和约数 素数和合数 1）d | a ，读作”d整除a”，表示a是d的倍数； 2）约数：d | a 且d>0，则d是a的约数；（即定义约数为非负整数） 3）对整数a最小约数为1，最大为|a|。其中，1和|a|为整数的平凡约数,而a的非平凡约数称为a的因子； 素数和合数 1) 素数(质数)：对于整数a > 1，如果它仅有平凡约数1和a，则a为素数； 2) 合数：不是素数的整数a ，且 a > 1; 3) 整数1被称为基数，它不是素数也不是合数； 4) 整数0和所有负整数既不是素数也不是合数； 2019/4/24

初等数论概念 已知一个整数n，所有整数都可以划分为是n的倍数的整数，以及不是n的倍数的整数。对于不是n的倍数的那些整数，又可以根据它们除以n所得的余数来进行分类。——数论的大部分理论都是基于这种划分 除法定理（Th31.1）： 其中，q为商，值r = a mod n称为余数。 根据整数模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 ( mod n ) 2019/4/24

初等数论概念 2019/4/24

初等数论概念 公约数：d是a的约数也是b的约数，则d是a和b的公约数。 公约数性质： 最大公约数： gcd基本性质： -- 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|; 2019/4/24

初等数论概念 最大公约数性质： 2019/4/24

初等数论概念 互质数：如果gcd(a,b)=1,则称a与b为互质数； 如果两个整数中每一个数都与一个整数p互为质数，则它们的积与p互为质数，即： 唯一因子分解： 定理31.7: 对所有素数p和所有整数a, b, 如果 p | ab，则 p | a 或 p | b（或者两者都成立） 2019/4/24

最大公约数 一种直观求解GCD： 根据a和b的素数因子分解，求出正整数a和b的最大公约数gcd(a,b)，即： 注：这种解法需要整数的素因子分解，而素因子分解是一个很难的问题（NP问题） 2019/4/24

最大公约数 欧几里得算法 Th.31.9（GCD递归定理）： 对任何非负整数a和正整数b，有gcd(a,b) = gcd(b, a mod b) ； * 可以通过证明gcd(a,b)与 gcd(b, a mod b)能相互整除来证明该定理！ P526 伪代码： Euclid(a, b) { if b=0 then return a; else return Euclid(b, a mod b); } 例子： Euclid( 30, 21 ) = Euclid ( 21, 9 ) = Euclid ( 9, 3 ) = Euclid ( 3, 0 ) 2019/4/24

最大公约数 Euclid算法的运行时间： 2019/4/24

最大公约数 扩展的Euclid算法： 2019/4/24

最大公约数 用计算gcd( 99, 78 )的例子说明Extended-Euclid的执行过程: a b floor(a/b) d x y 99 78 1 3 -11 14 78 21 3 3 -11 21 15 1 3 -2 15 6 2 3 1 -2 6 3 2 3 1 3 1 3 - (d, x, y) = ( a, 1, 0 ) 2019/4/24

模运算和模线性方程 群(S, ⊕)是一个集合S和定义在S上的二进制运算⊕，且满足封闭性、单位元、结合律、逆元等4个性质； 交换群（a ⊕ b = b ⊕ a）和有限群： 2019/4/24

模运算和模线性方程 其中，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 14

模运算和模线性方程 子群： 如果(S, ⊕)是一个群，S’是S的一个子集，并且（S’, ⊕) 也是一个群， 则(S’, ⊕)称为(S, ⊕)的子群。 下面定理对子群规模作出了一个非常有用的限制： 15

模运算和模线性方程 由a生成的子群用<a>或者(<a>,⊕)来表示，其定义如下： 由一个元素生成的子群： 从有限群(S, ⊕)中，选取一个元素a，并取出根据群上的运算由a所能生成的所有元素，这些元素构成了原有限群的一个子群。 * 在群 Zn 中，有a(k) = ka mod n； * 在群 中，有a(k) = ak mod n； 由a生成的子群用<a>或者(<a>,⊕)来表示，其定义如下： <a> = { a(k) : k ≥ 1 } 称为 a 生成子群<a>或者a是<a>的生成元。 2019/4/24

模运算和模线性方程 问题描述： 17

模运算和模线性方程 <a>群表示和构造定理 18

模运算和模线性方程 推论1： 方程ax ≡ b (mod n) 对于未知量x有解，当且仅当 gcd( a, n) | b。 推论2： 方程ax ≡ b (mod n)或者对模n有d个不同的解，其中 d = gcd(a, n)，或者无解。 2019/4/24

模运算和模线性方程 20

模运算和模线性方程 输入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” } 21

模运算和模线性方程 求解方法： 22

模运算和模线性方程 2019/4/24

中国余数定理 中国余数定理，也称中国剩余定理，孙子剩余定理。 从《孙子算经》到秦九韶《数书九章》对一次同余式问题的研究成果，在１９世纪中期开始受到西方数学界的重视。１８５２年，英国传教士伟烈亚力向欧洲介绍了 《孙子算经》的“物不知数”题和秦九韶的“大衍求一术”；１８７６年，德国人马蒂生指出，中国的这一解法与西方１９世纪高斯《算术探究》中关于一次同余式 组的解法完全一致。从此，中国古代数学的这一创造逐渐受到世界学者的瞩目，并在西方数学史著作中正式被称为“中国剩余定理”。 2019/4/24

中国余数定理 韩信点兵： 韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让 敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从１至５报数，也记下最后一个士兵所报之数；最后令士兵从1至7 报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。 这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的一次同余式解法。它是中国古代数学家的一项重大创造，在世界数学史上具有重要的地位。 2019/4/24

中国余数定理 用数学语言来表述就是如下线性同余方程 《孙子算经》实际上是给出了这类一次同余式组 的一般解： 最早提出并记叙这个数学问题的，是南北朝时期的数学著作《孙子算经》中的“物不知数”题目。这道“物不知数”的题目是这样的： “今有一些物不知其数量。如果三个三个地去数它，则最后还剩二个；如果五个五个地去数它，则最后还剩三个；如果七个七个地去数它，则最后也剩二个。问：这些物一共有多少？” 用数学语言来表述就是如下线性同余方程 《孙子算经》实际上是给出了这类一次同余式组 的一般解： 2019/4/24

中国余数定理 但由于题目比较简单，甚至用试猜的方法也能求得，所以《孙子算经》尚没有上升到一套完整的计算程序和理论的高度。 真正从完整的计算程序和理论上解决这个问题的，是南宋时期的数学家秦九韶。秦九韶在他的《数书九章》中提出了一个数学方法“大衍求一术”，系统地论述了一次同余式组解法的基本原理和一般程序。 如今，中国余数定理广泛应用于通信领域。譬如，电子工程师发明的“中国余数码” (Chinese Remainder Code) 是一种常用的纠错编码 (error correcting code)。 2019/4/24

中国余数定理 定理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； 2019/4/24

中国余数定理 a 模n的逆存在唯一性定理: 2019/4/24

中国余数定理 2019/4/24

谢谢！ Q & A 作业： 31.1-12 31.2-4 31.3-5 31.4-3 2019/4/24