网络信息安全课件第四章.ppt

文档介绍：网络信息安全课件第四章
*
*
第一页，共53页
本章要点
域是一些元素的集合，其上定义了两个算术运算(加法和乘法)，具有常规算术性质，如封闭性、结合律、交换律、分配律、加法逆和乘法逆等。
模算术是一种整数算术，它将所有整数约减为一个固定的集合[0,1,…,n-1]，n为某个整数。任何这个集合外的整数通过除以n取余的方式约减到这个范围内。
两个整数的最大公因子是可以整除这两个整数的最大正整数。
一个有限域就是有有限个元素的域。可以证明有限域的阶(元素个数)一定可以写作素数的幂形式pn，n为一个整数，p为素数。
阶为p的有限域可以由模p的算术来定义。
阶为pn，n>1的有限域可由多项式算术来定义。
*
*
第二页，共53页
, 环和域Groups, Rings, and Fields
群G, 记作{G, •}, 定义一个二元运算•的集合，G中每一个序偶(a, b)通过运算生成G中元素(a•b)，满足下列公理：
(A1) 封闭性Closure: 如果a和b都属于G, 则a•b也属于G.
(A2) 结合律Associative: 对于G中任意元素a, b, c，都有a•(b•c)=(a•b)•c成立
(A3) 单位元Identity element: G中存在一个元素e，对于G中任意元素a，都有a•e=e•a=a成立
(A4) 逆元Inverse element: 对于G中任意元素a, G中都存在一个元素a’，使得a•a’=a’•a=e成立
*
*
第三页，共53页
群、有限群和无限群
用Nn表示n个不同符号的集合，{1,2,…,n}. n个不同符号的一个置换是一个Nn到Nn的一一映射。定义Sn为n个不同符号的所有置换组成的集合。Sn中的每一个元素都代表集合{1,2,…,n}的一个置换，容易验证Sn是一个群：
A1：如果π,ρ∈Sn，则合成映射π•ρ根据置换π来改变ρ中元素的次序而形成，如，{3,2,1}•{1,3,2}={2,3,1},显然π•ρ ∈Sn
A2：映射的合成显而易见满足结合律
A3：恒等映射就是不改变n个元素位置的置换，对于Sn，单位元是{1,2,…,n}
A4：对于任意π∈Sn ，抵消由π定义置换的映射就是π的逆元，这个逆元总是存在，例如： {2,3,1}•{3,1,2}={1,2,3},
有限群Finite Group和无限群Infinite Group：如果一个群的元素是有限的，则该群称为有限群，且群的阶等于群中元素的个数；否则称为无限群
*
*
第四页，共53页
交换群和循环群
交换群Abelian Group：还满足以下条件的群称为交换群(又称阿贝尔群)
(A5) 交换律Commutative ：对于G中任意的元素a, b，都有a•b=b•a成立
当群中的运算符是加法时，其单位元是0；a的逆元是-a, 并且减法用以下的规则定义：
a – b = a + (-b)
循环群Cyclic Group
如果群中的每一个元素都是一个固定的元素a (a ∈G)的幂ak(k为整数)，则称群G为循环群。元素a生成了群G，或者说a是群G的生成元。
*
*
第五页，共53页
环 (Rings)
环R, 由{R, +, x}表示, 是具有加法和乘法两个二元运算的元素的集合，对于环中的所有a, b, c, 都服从以下公理：
(A1-A5), 单位元是0，a的逆是 -a.
(M1), 乘法封闭性, 如果a和b属于R, 则ab也属于R
(M2), 乘法结合律,对于R中任意a, b, c有a(bc)=(ab)c.
(M3), 乘法分配律, a(b+c)=ab+ac or (a+b)c=ac+bc
(M4), 乘法交换律, ab=ba，交换环
(M5), 乘法单位元, R中存在元素1使得所有a有 a1=1a.
(M6), 无零因子, 如果R中有a, b且ab=0, 则 a=0 or b=0.
满足M4的是交换环；满足M5和M6的交换环是整环
*
*
第六页，共53页
域 (Fields)
域F, 可以记为{F, +, x}, 是有加法和乘法的两个二元运算的元素的集合，对于F中的任意元素a, b, c, 满足以下公理：
(A1-M6), F是一个整环
(M7), 乘法逆元, 对于F中的任意元素a(除0以外), F中都存在一个元素a-1, 使得aa-1=(a-1)a=1.
域就是一个集合，在其上进行加减乘除而不脱离该集合, 除法按以下规则定义: a/b=a(b-1).
有理数集合, 实数集合和复数集合都是域；整数集合不是域，因为除了1和-1有乘法逆元，其他元素都无乘法逆元
*
*
第七页，共53页
群、环和域的关