信息安全原理与技术ch02-数学基础

《信息安全原理与技术ch02-数学基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息安全原理与技术郭亚军宋建华李莉清华大学出版社第2章数学基础主要知识点：--数论--代数基础--计算复杂性理论--单向函数2021/8/292Ch2-数学基础因子设Z表示全体整数所构成的集合。定义2.1设a,b∈Z，a≠0，c∈Z，使得b=ac，则称a整除b，并称a是b的因子或者约数，b是a的倍数，记为a

2、b。定理2.1（带余除法）设a,b∈Z，b≥1，则存在唯一的整数q和r，使得a=qb+r，0≤r

3、为0，如果c

4、a且c

5、b，则称c为a和b的公因子。特别地，我们把a和b的所有公因子中最大的，称为a和b的最大公因子，记为gcd(a,b)或者(a,b)。2021/8/293Ch2-数学基础计算两个数的最大公因子的最容易的方法是用欧几里德(Euclid)算法定理2.3（欧几里德算法）给定整数a和b，且b>0，重复使用带余除法，即每次的余数为除数去除上一次的除数，直到余数为0，这样可以得到下面一组方程：a=bq1+r1,0

6、r2,……rj-1=rjqj+1最后一个不为0的余数rj就是a和b的最大公因子2021/8/294Ch2-数学基础例2.1求gcd(1970，1066)用欧几里德算法的计算过程如下：1970＝1×1066+9041066＝1×904+162904＝5×162+94162=1×94+6894＝1×68+2668＝2×26+1626＝1×16+1016＝1×10+610＝1×6+46=1×4+24＝2×2+0因此gcd(1970，1066)=22021/8/295Ch2-数学基础素数定义2.4设p∈Z

7、，p≥2，如果p的正因子只有1和p，则称p为素数，否则为合数若正整数a有一因子b，而b又是素数，则称b为a的素因子如果整数a与整数b的最大公因子是1，即gcd(a,b)=1，则称a与b互为素数，简称互素设(m)为小于或等于m且与m互素的正整数个数，则称其为欧拉(Euler)函数2021/8/296Ch2-数学基础同余定义2.8两个整数a,b分别被m除，如果所得的余数相同，则称a与b对模m是同余的，记为a≡b(modm)，正整数m称为模数同余具有下面的性质：(1)若a≡b(modm)，则则m

8、(b

9、-a)。反过来，若m

10、(b-a)，则a≡b(modm)(2)如果a=km+b(k为整数)，则a≡b(modm)(3)每个整数恰与0,1,…，m-1这m个整数中的某一个对模m同余(4)同余关系是一种等价关系(5)a≡b(modm)当且仅当amodm=bmodm2021/8/297Ch2-数学基础定理2.8(乘法消去律)对于ab≡ac（modm）来说，若gcd(a,m)＝1则b≡c(modm)。定理2.9(加法消去律)如果a+b≡a+c（modm），则b≡c(modm)加法消去律是没有条件，但乘法消去

11、律的条件是gcd(a,m)＝1，即a和m互素例如6×3≡6×7≡2mod8，但3≡7mod8不成立2021/8/298Ch2-数学基础模运算求余运算称为模运算,下面是模运算的一些性质。(1)(a+b)modm=((amodm)+(bmodm))modm(2)(a-b)modm=((amodm)-(bmodm))modm(3)(a×b)modm=((amodm)×(bmodm))modm(4)(a×(b+c))modm=((a×b)modm)+((a×c)modm))modm例如11mod8=3;1

12、5mod8=7,那么(11mod8)+(15mod8)mod8=(3+7)mod8=2(11+15)mod8=26mod8=2在模运算中，加法单位元是0，(0+a)modm=amodm乘法单位元是1，(1×a)modm=amodm2021/8/299Ch2-数学基础定义2.13对a∈Zm，存在b∈Zm，使得a+b≡0(modm)，则b是a的加法逆元，记b=-a。定义2.14对a∈Zm，存在b∈Zm，使得a×b≡1(modm)，则称b为a的乘法逆元。加法一定存在逆元，乘法不一定存在逆元。在密码学特别

13、是非对称密码体制中，常常需要求模逆元，求模逆元就是求乘法逆元。即寻找一个x，使得a×x≡1modm成立求模逆元问题很困难，有时有结果，有时没有结果利用扩展欧几里德算法能够计算出模逆元2021/8/2910Ch2-数学基础模8运算的例子模8的加法和乘法运算与普通运算一样,只是将所得的值是去模8后的余数2021/8/2911Ch2-数学基础2021/8/2912Ch2-数学基础模8的加法逆元和乘法逆元对每一个x都有一个对应的y，使得x+y≡0mod8，则y是x的加法逆元。如对2，有6，