《第2章 信息安全数学基础(数论)ppt课件》由会员分享，可在线阅读，更多相关《第2章 信息安全数学基础(数论)ppt课件（144页珍藏版）》请在金锄头文库上搜索。
1、2020 5 18 电子科技大学计算机科学与工程学院 计算系统与网络安全ComputerSystemandNetworkSecurity 2020 5 18 子夏曰 贤贤易色 事父母 能竭其力 事君 能致其身 与朋友交 言而有信 虽日未学 吾必谓之学矣 人际关系 父子 君臣 朋友 夫妻 数论基础 2020 5 18 第2章信息安全数学基础 数论 2020 5 18 第2章信息安全数学基础 数论 2020 5 18 2 整除的基本性质 N 整数集 1 a a 0 a 0 a a 同理 b N 1 b 2 b a cb ca 3 a b b c a c 传递性 4 a b a c a xb yc
2、x y N 5 b a且a 0 b a 6 cb ca b a 1 定义 设整数a和b 且a 0 如果存在整数k使得b ak 那么就说a整除a 或b能被a整除 记作a b 或者说b是a的倍数 举例 3 15 15 60 整除定义及性质 2020 5 18 证明 1 作一个整数序列 2 反证法 带余数除法 如果a b是两个整数 其中b 0 则存在两个整数q和r 使得a bq r 0 r b 成立 且q和r是唯一的 带余数除法 2020 5 18 非负最小剩余的性质 1 2 3 定义 非负最小剩余 a bq r 0 r b 中r叫做非负最小剩余 常记做b r 在不致引起混淆的情况下 b常常省略 带
3、余数除法 2020 5 18 1 定义 一个大于1的整数p 只能被1或者是它本身整除 而不能被其他整数整除 则称整数为素数 primenumber 否则就叫做合数 composite eg素数 2 3 5 7 11 13等 合数 4 6 8 9 12等 素数定义及素数个数定理 2020 5 18 2 补充定理 1 设a是任一大于1的整数 则a的除1外的最小正因子q是素数 并且当a是合数时 素数补充定理 2020 5 18 2 补充定理 2 若p是一个素数 a是任一整数 则有p a或 p a 1 素数补充定理 续 2020 5 18 素数补充定理 续 2 补充定理 p为素数 且p ab 那么p
4、a或p b 更一般地 如果ab z能够被素数p整除 那么a b z中的某个数必能被p整除 2020 5 18 3 素数个数定理 1 素数的个数是无限的 原因 1 N N 1 的除1外的最小正因数q是一个素数 2 如果q pi i 1 2 k 且q N 因此q N p1p2 pk 所以q 1 与q是素数矛盾 素数个数定理及证明 证明 反证法假设正整数个数是有限的 设为p1 p2 pk令 p1p2 pk 1 N N 1 则N有一个素数p 且p pi i 1 2 k 故p是上述k个素数外的另外一个素数 因此与假设矛盾 2020 5 18 素数定义及素数个数定理 3 素数个数定理 2 设 x 是小于x
5、的素数个数 则 x x lnx 即x 时 比值 x x lnx 1eg 可以估算100位素数的个数 10100 1099 10100 ln10100 1099 ln1099 3 9 1097 2020 5 18 1 整数的唯一分解定理定理 算术基本定理 设n Z 有分解式 n p1e1p2e2 pmem 其中p1 p2 pm Z 是互不相同的素数 e1 e2 em Z 并且数对 p1 e1 p2 e2 pm em 由n唯一确定 即如果不考虑顺序 n的分解是唯一的 eg 504 23327 1125 3253 整数的唯一分解定理 2020 5 18 1 定义两个整数a b的最大公约数 就是能同时
6、整除a和b的最大正整数 记为gcd a b 或 a b eg gcd 5 7 1 gcd 24 60 12 最大公约数定义及求法 2 求最大公约数的两种方法 1 因数分解 eg 1728 2632 4536 23347 gcd 1728 4536 2332 72 2020 5 18 2 欧几里得 Euclid 算法设a b N a b 0 用以下方法可求出gcd a b 最大公约数的欧几里得算法 2020 5 18 Euclid算法实例 求gcd 132 108 最大公约数的欧几里得算法 续 2020 5 18 欧几里得算法 例1 gcd 1180 482 2 求 gcd 1180 482 最
7、大公约数的欧几里得算法 续 2020 5 18 欧几里得算法 例2 求gcd 12345 1111 最大公约数的欧几里得算法 续 2020 5 18 欧几里得算法抽象 规律 余数 除数 被除数 忽略 最大公约数的欧几里得算法 续 2020 5 18 欧几里得算法实现 最大公约数的欧几里得算法 续 2020 5 18 特别a b为素数时gcd a b 1 存在ma nb 1 上述求rn ma nb的方法叫做扩展的Euclid算法利用该方法我们可以求ax by d的解 这里d a b 证明 根据Euclid算法a bq1 r1b r1q2 r2r1 r2q3 r3 rn 2 rn 1qn rngc
8、d a b rn rn 2 rn 1qn ma nb 3 定理设a b Z 则存在m n Z使得gcd a b ma nb 扩展的欧几里得算法 2020 5 18 计算出了gcd a b 但是并没有计算出两个数m n来 使得 ma nb gcd a b 扩展的欧几里得算法的结果 计算出了gcd a b 计算出两个数m n来 使得 ma nb gcd a b 扩展的欧几里得算法 续 欧几里得算法的结果 2020 5 18 利用该方法我们可以求密码学方程ax by d的解 这里d a b 例如 求132x 108y 12的解 解 12 gcd 132 108 12 108 4 24 108 4 1
9、32 108 1 108 4 132 4 108 5 108 4 132 扩展的欧几里得算法 续 2020 5 18 第2章信息安全数学基础 数论 2020 5 18 证明 必要性 设a b modm a mp r b mq r 0 r m a b m p q m a b 充分性 设m a b a mp r b mq s 0 r s m a b m p q r s m r s 0 r s m r s a b modm 证毕 2 定理设a b Z m Z 则a b modm m a b 1 定义设a b Z m Z 如果a和b被m除所得余数相同 则称a和b关于模数m同余 记为a b modm 同
10、余 2020 5 18 4 模运算的性质设m Z a b modm x y modm 则有 1 a x b y modm 加法 2 a x b y modm 减法 3 ax by modm 乘法 3 同余的性质设a b Z m Z 1 自反性 a Z a a modm 2 对称性 a b modm b a modm 3 传递性 a b b c modm a c modm 同余及模运算性质 2020 5 18 例 求解2x 7 3 mod17 解 2x 3 7 2x 4x 2x 15 mod17 4 模运算的性质 4 除法 相对复杂如果 12x 24 那么 3x 8如果 12x 24 mod3
11、那么 3x 8 mod3 定理 设整数a b c n n 0 gcd a n 1 如果ab ac modn 则b c modn 计算成立的原因 gcd 2 17 1 模运算的除法运算及其性质 2020 5 18 4 模运算的性质 4 除法 例 求解5x 6 13 mod11 解 5x 13 6 5x 7 mod11 x 7 5 注意到7 18 29 40 mod11 所以 5x 7 mod11 5x 40 mod11 x 8 mod11 计算成立的原因 gcd 5 11 1 模运算的除法运算及其性质 续 2020 5 18 5 模m的乘法逆元定义 设m Z x y Z 如果xy 1 modm
12、则称y是x的模m乘法逆元 记为 y x 1 乘法逆元 eg 2 3 1 mod5 3是2的模5乘法逆元 2是3的模5乘法逆元 2 8 1 mod5 8是2的模5乘法逆元 注意 模m乘法逆元不唯一 但是 如果求一个与模数互素的数的乘法逆元 则是唯一的 2020 5 18 欧几里德算法与乘法逆元如果算法gcd a b 输出rm 1 则b有乘法逆元如果求出了ma nb 1中的整数m n 则可以求出b moda 的乘法逆元 欧几里得算法没有给出b的乘法逆元b 1如何求b 1 扩展的欧几里德算法 扩展欧几里德算法与乘法逆元 2020 5 18 扩展欧几里德算法与乘法逆元 续 2020 5 18 例 求2
13、8mod75的乘法逆元 a 75 b 28 扩展欧几里德算法与乘法逆元 续 2020 5 18 扩展欧几里德算法 2020 5 18 例如 m 3C0 3qC1 3q 1C2 3q 2 定义 剩余类 设m是一个给定的正整数 Cr r 0 1 2 m 1 表示所有形如qm r的整数组成的集合 其中q 0 1 2 则C0 C1 Cm 1叫做模数m的剩余类 剩余类和完全剩余系 2020 5 18 2 充分条件 设a和b都包含在Cr中 则有 a q1m r b q2m r 因此 a b q1 q2 m 即m a b 必要条件 反之 如果m a b a和b模m同余 因此属于同一个Cr 原因 a和b模m同
14、余的充要条件是m a b 证明 1 由于a qm r 因此a恰好包含在Cr中 定理 设m 0 C1 Cm 1是模数m的剩余类 则有 1 每一个整数恰好包含在某一个类Cj中 0 j m 1 2 两个整数x和y属于同一个类的充要条件是x y modm 剩余类和完全剩余系 续 2020 5 18 定义 完全剩余系 在模数m的剩余类C1 Cm 1中各取一数aj j 0 1 m 1 此m个数a0 a1 am 1称为模数m的一组完全剩余系 剩余类和完全剩余系 续 例如 m 3C0 0 3 6 9 C1 1 4 7 10 C2 2 5 8 11 则a0 0 a1 1 a2 2就是模m的一组完全剩余系 202
15、0 5 18 定理 完全剩余系 m个整数组成模数m的一组完全剩余系的充要条件是两两对模数m不同余 剩余类和完全剩余系 续 定义 非负最小完全剩余系 由0 1 2 m 1组成的剩余系称为模数m的非负最小完全剩余系 2020 5 18 定理 完全剩余系 设 k m 1 a0 a1 am 1是模数m的一组完全剩余系 则 ka0 ka1 kam 1也是模数m的一组完全剩余系 剩余类和完全剩余系 续 2020 5 18 1 剩余类可能包含多个集合 即 模数m的剩余类是多个集合 2 完全剩余系专指一个集合 剩余类和完全剩余系 续 定义 模数m互素的剩余类 如果一个模数m的剩余类里面的数与m互素 就称之为与
16、模数m互素的剩余类 例如 m 3C1 1 4 7 10 C2 2 5 8 11 都是模m互素的剩余类 2020 5 18 定义 缩系 在与模数m互素的全部剩余类中 各取一个数所组成的集合叫做模数m的一组缩系 剩余类和完全剩余系 续 例如 m 3C1 1 4 7 10 C2 2 5 8 11 是模m互素的剩余类 而C 4 5 是模数m的一组缩系 问题 缩系含有多少个数 2020 5 18 欧拉函数的求法 1 如果n是素数 则 n n 1 2 n pq 其中p q为素数 则 n p 1 q 1 3 1 定义 欧拉函数 欧拉函数 n 是一个定义在正整数上的函数 n 的值等于序列0 1 2 n 1中与n互素的数的个数 费马小定理和欧拉定理 2020 5 18 定理 缩系中数的个数 模数m的缩系含有 n 个数 费马小定理和欧拉定理 续 例如 m 3 m 2 因而C 1 2 含有两个数 定理 缩系 若a1 a2 a m 是 m 个与m互素的整数 则a1 a2 a m 是模数m的一组缩系的充要条件是它们两两对模数m不同余 2020 5 18 定理 若 a m 1 x通过模数m的缩系 则ax也通过模数
