02-1 数论与代数.ppt

信息安全数学基础 数论与代数 数论 用Z表示整数集 3 2 1 0 1 2 3 定义1设a b Z a 0 如果存在c Z 使得b ac 则称a整除b 并称a是b的因子 b是a的倍数 记为a b 如果不存在整数c 使得b ac 则称a不能整除b 记为ab定理 带余除法 设a b Z b 1 则存在唯一确定的整数q和r 使得a qb r 0 r b q称为a除以b所得的商 r称为a除以b所得的余数 通常记r amodb 例 设a 73 b 17 则q 4 r 5 73mod17 5 定义2设a b Z a b不全为0 如果c a且c b 则称c为a和b的公因子 特别地 我们把a和b的所有公因子中最大的 称为a和b的最大公因子 我们知道 每个非零整数只有有限多个因子 所以若a和b是两个不全为0的整数 则它们的公因子也只有有限多个 所以 它们的最大公因子必然存在 而且唯一 将这个最大公因子记为gcd a b 定义3设a b Z a b不全为0 如果a D b D且D 1 则称D为a和b的公倍数 特别地 我们把a和b的所有公倍数中最小的正的公倍数 称为a和b的最小公倍数 a和b的最小公倍数一定存在而且唯一 将这个最小公倍数记为lcm a b 对两个正整数a和b 必有ab gcd a b lcm a b 定义4设p Z p 2 如果p只有正因子1和p 则称p为一个素数 否则称p为一个合数 定义5设n 1 表示在区间 1 n 中与n互素的整数的数目 函数称为Euler函数 关于Euler函数有以下性质 1 如果p是素数 则 p 1 2 Euler函数是一个积性函数 也就是说 如果gcd m n 1 则 3 如果是n的一个典型分解式 则 虽然我们可以通过分解两个正整数a和b来计算它们的最大公因子 但是目前还没有分解整数的有效算法 这里我们来描述一个计算两个整数的最大公因子的有效算法 称为Euclidean算法 其理论依据是 如果a b是两个正整数 a b 则gcd a b gcd b amodb 同余 设n为正整数定义6设a b Z 如果n a b 则我们说a和b模n同余 记为a b modn 整数n称为同余模 例 1 24 9 mod5 因为24 9 3 5 2 11 17 mod7 因为 11 17 4 7 同余式具有下列一些基本性质 1 a b modn 当且仅当amodn bmodn 2 反身性 a a modn 3 对称性 如果a b modn 那么b a modn 4 传递性 如果a b modn b c modn 那么a c modn 5 如果a a1 modn b b1 modn 那么a b a1 b1 modn ab a1b1 modn 对模的理解 模就是周而复始 螺旋上升 到了终点就是回到了起点 比如钟表 模为12 1 13 mod12 23 11 mod12 1 11 mod12 5 7 mod12 欧几里得算法和扩展欧几里德算法 欧几里德算法又称辗转相除法 用于计算两个整数a b的最大公约数 其计算原理依赖于下面的定理gcd a b gcd b amodb 证明a可以表示成a kb r 则r amodb 假设d是a b的一个公约数 则有d a d b 而r a kb 因此d r 因此d是 b amodb 的公约数 假设d是 b amodb 的公约数 则d b d r 因a kb r因此d也是 a b 的公约数 因此 a b 和 b amodb 的公约数是一样的 其最大公约数也必然相等 得证 欧几里得算法和扩展欧几里德算法 首先描述Euclidean算法的基本形式 它可以给出两个正整数a和b的最大公因子 Euclidean算法首先令r0为a 令r1为b 然后执行如下除法运算 r0 q1r1 r2 0 r2 r1r1 q2r2 r3 0 r3 r2 rm 2 qm 1rm 1 rm 0 rm rm 1rm qmrm容易看到gcd r0 r1 gcd r1 r2 gcd rm 1 rm rm因此可以得出gcd a b rm 欧几里得算法和扩展欧几里德算法 例设a 4864 b 3458 按上述算法计算gcd 4864 3458 的步骤如下 4864 1 3458 14063458 2 1406 6461406 2 646 114646 5 114 76114 1 76 3876 2 38 0故gcd 4864 3458 38 欧几里得算法和扩展欧几里德算法 欧几里得算法和扩展欧几里德算法 扩展欧几里德定理对于与不为0的非负整数a b gcd a b 表示a b的最大公约数 那么存在整数x y使得gcd a b ax by 若gcd a b 1 ax by 1于是得ax 1 modb by 1 moda x为a模b的乘法逆元 y为b模a的乘法逆元 例如要计算5模26的乘法逆元 26x 5y gcd 26 5 则只需要计算y 欧几里得算法和扩展欧几里德算法 求解x y的方法的理解我们不妨设a b 1 显然当b 0 gcd a b a 此时x 1 y 0 2 ab0时 设ax1 by1 gcd a b bx2 a b y2 gcd b a b 根据欧氏定理gcd a b gcd b a b 则ax1 by1 bx2 a b y2 即ax1 by1 bx2 a a b b y2 ay2 bx2 a b by2 根据恒等定理得 x1 y2 y1 x2 a b y2 这样我们就得到了求解x1 y1的方法 x1 y1的值基于x2 y2 上面的思想是递归定义了 因为gcd不断的递归求解一定会有个时候b 0 所以递归可以结束 欧几里得算法和扩展欧几里德算法 开始计算计算b 5模a 26的逆元 带入ax by gcd a b 得26x 5y gcd 26 5 计算步骤迭代 26x 5y gcd 26 5 迭代 5x 1y gcd 5 1 最大公约数gcd a b 1迭代5x 1y gcd 5 1 则x 0 y 1a 5 b 1 x 0 y 15 0 1 1 gcd 5 1 迭代26x 5y