lect欧ure04密码学的数学引论.ppt

§4－2　群论 群的概念 是由一个非空集合G组成，在集合G中定义了一个二元运算符“· ”，并满足以下性质的代数系统，记为｛G, · ｝ 交换群： 有限群 无限群 有限群的阶 循环群 循环群的生成元 群的性质 群中的单位元是唯一的 群中每一个元素的逆元是唯一的 (消去律) 对任意的　　　，如果 ，或　　　，则 §4－3　有限域理论 域的概念 域是由一个非空集合F组成，在集合F中定义了两个二元运算符：“+”和“· ”，并满足： 域记为｛F,+,·} 两个定义： 有限域 有限域的阶 域的实质： 域是一个可以在其上进行加法、减法、乘法和除法运算 而结果不会超出域的集合。如有理数集合、实数集合、 复数集合都是域，但整数集合不是 减法：a-b=a+(-b) 除法：a/b=a·(b-1) 有限域的两个定理 密码学常用素域GF(p)或阶为2m的域GF(2m) GF(p)有限域中的计算 生成元与逆元 生成元 可证明：在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次方幂的形式，g称为GF(p)的生成元 逆元 生成元的例子 有限域GF（23），5是GF（23）的生成元 50＝1 51＝5 52＝2 53＝10 54＝4 55＝20 56＝8 57＝17 58＝16 59＝11 510＝9 511＝22 512＝18 513＝21 514＝13 515＝19 516＝3 517＝15 518＝6 519＝7 520＝12 521＝14 522＝1 GF（2m)域 生成元与逆元 生成元： 逆元 例子：GF（24） 取： GF（24）的元素： （0000） (0001) (0010) (0011) (0100) (0101) (0110) (0111) (1000) (1001) (1010) (1011) (1100) (1101) (1110) (1111) 例子（续） 生成元为：a=x * 计算a和b的最大公约数。 直到r=0为止，其前一个r即为两个数的最大公约数。 * 直到r＝0时计算终止。i从－2开始，实际上，i从0开始也可。 * 计算到r＝0为止。 * 标题为“欧拉函数”。 * 欧拉定理。 第四章　密码学的数学引论 学习要点： 了解数论、群论、有限域理论的基本概念 了解模运算的基本方法 了解欧几里德算法、费马定理、欧拉定理、中国剩余定理 了解群的性质 了解有限域中的计算方法 1、除数(因子)的概念：设z为由全体整数而构成的集合，若 b≠0且 　　　　使得a=mb,此时称b整除a.记为b∣a,还称b为a的除数(因子). 注:若a=mb+r且0rb,此时b不整除a,记为 2、质数(质数)的概念:整数p1被称为质数是指p的因子仅有1,-1,p,-p。 §4－1　数论 §算术基本定理： 任何一个不等于0的正整数a都可以写成唯一的表达式a＝P1α1P2α2…Ptαt，这里P1＜P2＜P3…＜Pt是质数，其中αi0 §最大公约数： 若a,b,c∈z，如果c∣a，c∣b，称c是a和b的公约数。正 整数d称为a和b的最大公约数，如果它满足 d是a和b的公约数。 对a和b的任何一个公约数c有c∣d。 注：1*. 等价的定义形式是： gcd（a,b）＝max{k∣ k∣a且k∣b} 2*．若gcd（a,b）=1，称a与b是互素的。 带余除法：?a∈z,0，可找出两个唯一确定的整数q和r,使a=qm+r, 0=r m,q和r这两个数分别称为以m去除a所得到的商数和余数。 (若r=0则m∣a） 整数同余： 定义：如果a mod m =b mod m，则称整数a模正整数m同余于整数b，并写a≡b（mod m）是指m∣（a－b）, m称为模数。注：1*.m∣a-b?a=q1m+r,b=q2m+r即a和b分别 除以m有相同的余数。“同余”二字的来源就在于此。 二、模算术 2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质： 自反性：对任意整数a有：a≡a（mod m） 对称性：如果a≡b(mod m)，则b≡a（mod m） 传递性：如果a≡b (mod m）b≡c（mod m），则a≡c(mod m) 于是，全体整数集合z可按模m（m1）分成一些两两不交的等价类。 3*. 对于某个固定模m的同余式可以象普通的等式那样相加、相减和相乘，可结合： (1)[a(mod m)±b(mod m)]mod m=(a±b)(mod m) (2)[a(mod m)*b(mod m)]mod m=a*b(mod m) (