离散数学讨论课(群环格域布尔代数)课件.pptx

《离散数学讨论课(群环格域布尔代数)课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散讨论课（常见群、环、域、格和布尔代数在计算机中的应用）群论半群单元半群群的基本定义交换群有限群循环群半群：设有一个代数系统(S,。)其中“。”是二元运算，它满足结合律，则称该代数系统为半群，对S内任意元素a，b，c有(a。b)。c=a。(b。c)如果半群还满足交换律，则称其为可换半群。单元半群：设有一个代数系统(S,。)其中“。”是二元运算，它满足结合律，并且存在单位元素，则此代数系统叫做单元半群。即对S内任意元素a，b，c有(a。b)。c=a。(b。c)且存在1∈S有1.a=a。1=a。如果单元半群还满足交换律，则称其为

2、可换单元半群。群论：（1）、满足结合律。（2）、存在单位元素。（3）、存在逆元素。则称该代数系统为群。可换群也叫阿贝尔群。有限群：群的元素个数有限，则称为有限群，反之元素个数无限，则称为无限群。循环群：若群（G，。）中的每一个元素都是它的某一固定元素a的幂，则称（G，。）为由a生成的循环群，a称作（G，。）的生成元素。剩余类加群：（Zm，+m）是一个群，周期为m的循环群，[0]为其单位元素，[i]+[0]=[i]，[i]m=[0]=１。整数加群：（Ｚ，+）是一个周期为无限的循环群。设有一个由ａ生成的循环群（Ｇ，。），则有：（１

3、）、若ａ周期为无限，则（Ｇ，。）与（Ｚ，+）同构。（２）、若ａ周期为ｍ，则（Ｇ，。）与（Ｚｍ，+ｍ）同构。群论在计算机领域的应用：（１）、组合群论在密码学中的应用（２）、用群论的基础知识理解信号处理中的一些基本概念（如：时域和频域信号空间的群同构关系）（３）、椭圆曲线密码的应用等组合群论在密码学中的应用用群论的基础知识理解信号处理中的一些基本概念(如：时域和频域信号空间的群同构关系)椭圆曲线密码的应用椭圆曲线密码的应用无线网络操作模式由3部分组成:①移动用户。能从一个代理范围移动到另一个代理范围;②地点固定的代理。它如同一个调

4、停机构,协调移动用户和服务器之间的通信服务;③服务器。当移动用户从一个地区到另一个地区时,它能选择一个合适的代理,实现与服务器和其它移动用户之间的通信。为了保证用户的合法接入和信息的安全传输,一般需要做到如下5点：【1】访问控制。确保接入用户合法。此过程可以通过移动用户的MAC地址和用户的相关信息来实现。【2】身份认证。确保对方为其所声称的用户及数据的完整性,通过数字签名技术实现。【3】不可否认性。确保其发出的信息事后无法抵赖,通过数字签名实现。【4】数据完整性。防止信息被截获后数据被更改重新发送,通过消息认证码(MAC)和数

5、字签名来实现。【5】保密性。信息在传输中即使被截获,因截获者无法破解而毫无意义。通过数据的加密来实现。密码应用中常使用的两类椭圆曲线为定义在有限域GF(p)上的素曲线和在有限域GF(2n)上的二元曲线。素曲线计算不需二元曲线所要求的位混淆运算,对软件应用而言,最好使用素曲线;而对硬件应用而言,则最好使用二元曲线,它可用很少的门电路来得到快速且功能强大的密码体制。椭圆曲线的加密和解密在SEC1的椭圆曲线密码标准(草案)中规定,一个椭圆曲线密码由下面的6元组所描述:T=式中:p为大于3的素数,它确定了有限

6、域GF(p);a和b确定了椭圆曲线;G为循环子群E1的生成元;n为素数且为生成元G的阶,G和n确定了循环子群E1;h为余因子,有h=

7、E1

8、/n,h将交换群E和循环子群联系起来。用户的私钥定义为一个随机数dd∈{0,1,2,⋯,n-1}用户的公开密钥定义为Q点：Q=dG设要加密的明文数据为M,将M划分为一些较小的数据块,M=[m1,m2,⋯,mt]。式中:0≤mi

9、-1}。【3】用户A计算点X1:(x1,y1)=dAG。【4】用户A计算点X2:(x2,y2)=dAQB,如果分量x2=0,则转【2】。【5】用户A计算C=mix2modn。【6】用户A发送加密数据(X1,C)给用户B。解密过程：【1】B用自己的私钥dB求出点X2:dBX1=dB(dG)=dA(dBG)=dAQB=X2:(x2,y2)【2】对C解密,得到明文数据mi=Cx2-1modn。与此类似,可以构造其他椭圆曲线密码。环论和格论环的基本定义整环域格的基本定义分配格有界格补格布尔代数环的定义：设有代数系统（Ｒ，+，。），若满

10、足以下条件：（１）、（Ｒ，+）为可换群；（即满足交换律、结合律、存在零元、负元）（２）、（Ｒ，。）为半群；（即满足结合律）（３）、运算。对+满足分配律，即对任意ａ，ｂ，ｃ∈Ｒ，存在ａ。（ｂ+ｃ）＝ａ。ｂ+ａ。ｃ（ｂ+ｃ）。ａ＝ｂ。ａ+ｃ。ａ整环：（Ｒ，+，。）为环，它有单位元