高中数学选修5-3(密码学算法基础) 选修课密码学4 课件.ppt

密码学的数学基础 二 密码学概论 本讲授课提纲 1 整除 复习 2 素数 复习 3 最大公约数 4 欧几里德算法 复习 整除 定义 设整数a和b 且a 0 如果存在整数k使得b ak 那么就说b能被a整除 记做a b 或者说b是a的倍数 举例 3 15 15 60 整除 性质一 a 1 那么a 1 性质二 a b且b a 则a b 性质三 对任一b b 0 b 0 性质四 b g b h 则对任意整数m n有b mg nh 复习 素数 素数的定义如果整数p p 1 只能被1或者是它本身整除 而不能够被其它整数整除 则称整数p为素数 质数 最小的素数是2 1不是素数 大于1的整数如果不是素数 则称为合数 素数 素数有多少个呢 素数有无穷多个 素数定理给出一种估计素数个数的方法 设 x 是小于x的素数的个数 则 x x lnx素数的数量很多仅100位的素数约有3 9 1097个 素数 因素分解每一个整数都是由一个或者几个素数的不同次幂相乘得来得 比如504 23 32 7这种因式分解是唯一的 除非颠倒因子的顺序 也就是说 504因素分解总是得到三个2 两个3 一个7 素数 因素分解唯一性定理 算术基本定理 任何一个正整数都可以分解为几个素数的乘积 且该因素分解是唯一的 除非颠倒因子的顺序 任一整数a a 1 都能惟一地分解为以下形式 素数 性质一 两数相乘等价于这两个数的分解式中相同因子的指数相加 即由k mn 可得 对每一素因子p kp mp np 性质二 若a b 且a和b的分解式中 都有素p的幂 则对每一素数p的幂指数ap和bp 有ap bp 本讲授课提纲 1 整除 2 素数 3 最大公约数 4 欧几里德算法 最大公约数 最大公约数的定义a和b的最大公约数 GreatestCommonDivisor 是能够同时整除a和b的最大正整数 记为gcd a b 或者 a b 例如 gcd 6 4 2 gcd 5 7 1 gcd 24 60 12 互素的定义如果gcd a b 1 就称a和b互为素数 简称互素 最大公约数 求最大公约数的因数分解法把a和b因素分解 比较每一个素数在a和b因素分解中的幂的大小 取较小的一个 将所有素数的幂相乘即可得到gcd 举例gcd 1728 135 gcd 2632 355 32 9gcd 253472 22537 22305071 227 28 本讲授课提纲 1 整除 2 素数 3 最大公约数 4 欧几里德算法 欧几里德算法 欧几里德算法的来历计算两个数最大公约数最容易的方法是欧几里德算法 因为它不需要因数分解 速度快 欧几里德在公元前300年所写的Elements一书中描述了这个算法 这个算法并非由他发明 历史学家相信在当时也有200年历史 也就是距今已有2500年历史 它是幸存到现在最古老的非凡算法 至今它仍然是完好的 欧几里德算法 欧几里德算法的简单描述欧几里德算法又称 辗转相除法 其算法可简单描述如下 对于两个正整数 取其中较大者为被除数 较小者为除数 对这两个数做除法运算 得到商和余数 把除数作为被除数 把余数作为除数 重复上述过程 直到余数为零 最后一个非零的余数就是最大公约数 欧几里德算法 举例说明欧几里德算法例 计算gcd 482 1180 取较大数1180为被除数 较小数482为除数 做除法1180 2 482 216原来的除数482作为被除数 余数216作为除数 继续482 2 216 50216 4 50 1650 3 16 216 8 2 0 最后一个非零的余数即为所求最大公约数 欧几里德算法 举例说明欧几里德算法例 计算gcd 12345 11111 取较大数12345为被除数 较小数11111为除数 做除法12345 1 11111 1234原来的除数11111作为被除数 余数1234作为除数 继续11111 9 1234 51234 246 5 45 1 4 14 4 1 0 最后一个非零的余数即为所求最大公约数 欧几里德算法 欧几里德算法的精确描述两个整数用a b表示 商用q表示 余数用r表示Step1取a