中国余数定理韩信点兵.ppt

中国余数定理 定理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； * * 中国余数定理 a 模n的逆存在唯一性定理: * * 中国余数定理 * * 谢谢！ * * Q A 作业： 31.1-12 31.2-4 31.3-5 31.4-3 * University of Science and Technology of China University of Science and Technology of China University of Science and Technology of China University of Science and Technology of China University of Science and Technology of China * * * 第十四讲 有关数论算法 内容提要： 初等数论概念 最大公约数 模运算和模线性方程 中国余数定理 初等数论概念 整除性和约数 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和所有负整数既不是素数也不是合数； * * 初等数论概念 已知一个整数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 ) * * 初等数论概念 * * 初等数论概念 公约数：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问题） 最大公约数 欧几里得算法 Th.3