密码学与网络安全-第四章 密码数学基础(B).ppt

例：取 M(x) = x4+1 设 ，则 可以用矩阵表示运算结果 GF(28)上的矩阵运算表示两个多项式的乘法。 可表示为： 可表示为： 可表示为： 习题4 （p110） 24，25，26，31，32，33，37* LOGO 第四章 密码学基础(B) 代数结构 —— 群、环、域 §1 代数结构 一、 群(group) 定义 2.1 设G为一非空集合, ?为定义在G上的二元运算. 如果下述条件成立, 则称代数系统?G, ? ?为一个群. (1) 运算封闭性: ?a, b?G, a?b?G; (2) 结合律: ?a, b, c?G, a?(b?c)=(a?b)?c; (3) 存在单位元 e?G: 使得对?a?G, a?e=e?a=a; (4) ?a?G, 存在a的逆元 a?1?G: 使得 a?a?1= a?1?a=e. (5) 交换律：?a，b ?G, a?b= b?a. 交换群 例1 G = ? Zn, + ? （模 n +) 为一个群, 且是交换群。 单位元为 0 mod n a 的逆元是 – a mod n= n-a 例2 G = ? Z*n, × ? （模 n ×) 为一个群, 且是交换群。 单位元为 1 mod n a 的逆元是 a -1 mod n 例3 A={a, b, c, d}, G = ?A , · ? 是交换群。 运算表： · a b c d a a b c d b b c d a c c d a b d d a b c 单位元: a 逆元对: (a,a) , (b,d), (c,c) 例4 置换群（permutation group） 设 (1,2,3) 的所有置换构成集合 T={(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2),(3,2,1)} 在T上规定二元运算 ⊙ 为两个置换的复合： (2,1,3)⊙(2,3,1) =(1,3,2) ⊙ (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1) (1,2,3) (1,2,3) (1,3,2) (1,2,3) (2,1,3) (1,2,3) (3,2,1) (2,3,1) (1,3,2) (1,2,3) (3,1,2) (1,2,3) (3,2,1) (1,2,3) 则G = ? T, ⊙ ? 为一个群, 但不是交换群。 单位元为恒等置换 e ={ 1,2,3} a 的逆元是 a 的逆置换 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 （2 1 3 ） （2 3 1 ） （1 3 2 ） 定义 设 ?G, ? ? 是一群, H是G的一非空子集. 如果 ?H, ? ? 也是群, 则称 ?H, ? ? 是 ?G, ? ? 的一个子群. 定义 设 ?G, ? ? 是一群, 若G的元素个数有限， 则称 ?G, ? ? 是有限群(finite group). |G| 表示G的元素个数，称为G的阶。 在模 n 加法运算下，Zn 是n阶有限群。 定义 设 ?G, ? ? 是一群, 若G的元素可以由一个元素及其 幂组成，则称 ?G, ? ? 是循环群（cyclic group). 在 n 阶循环群中，生成元素为 g , G={e, g, g2, … gn-1 } , gn = e 循环群的生成元素可能不只一个！ 例6 在 G= ?Z*10 , * ? 中, Z*10 ={1,3,7,9}, 有循环子群： H1= ?{1}, × ?, 生成元是 1 H2= ?{1，9}, × ?，生成元是9 H3= G, 生成元是3, 或 7 例5 在 G= ?Z6 , + ? 中, 有循环子群：