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

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

2、，b，c有(a。b)。c= a。(b。c)且存在1S有1.a=a。1=a。如果单元半群还满足交换律，则称其为可可换单元半换单元半群群。群群 论论：（1）、满足结合律。 （2）、存在单位元素。 （3）、存在逆元素。则称该代数系统为群群。可换群也叫阿贝尔群。可换群也叫阿贝尔群。有有 限限 群群：群的元素个数有限，则称为有限群，反之元素个数无限，则称为无限群。循循 环环 群群：若群（G，。）中的每一个元素都是它的某一固定元素某一固定元素a的幂的幂，则称（G，。）为由a生成的循环群循环群，a称作（G，。）的生成生成元素元素。剩余类加群剩余类加群：（Zm，+m）是一个群，周期为m的循环群，0为其单位元素

3、，i+0=i，im= 0=。整数加整数加群群：（，+）是一个周期为无限的循环群。设有一个由生成的循环群生成的循环群（，。），则有：（）、若周期为无限，则（，。）与（，与（，+）同构）同构。（）、若周期为，则（，。）与（与（，+）同构同构。群论群论在计算机领域的应用：在计算机领域的应用：（）、组合群论在密码学中的应用组合群论在密码学中的应用（）、用群论的基础知识理解信号处理中用群论的基础知识理解信号处理中的一些基本概念（如：时域和频域信号空间的群同的一些基本概念（如：时域和频域信号空间的群同构关系）构关系）（）、椭圆曲线密码的应用等椭圆曲线密码的应用等组合群论在密码学中的应用组合群论在密码学中的

4、应用用群论的基础知识理解信号处理中的一些基本用群论的基础知识理解信号处理中的一些基本概概念念( (如如：时域和频域信号空间的群同构关：时域和频域信号空间的群同构关系系) )椭圆曲线密码的应椭圆曲线密码的应用用椭圆曲线密码的应用无线网络操作模式由 3 部分组成 : 移动移动用户用户。 能从一个代理范围移动到另一个代理范围 ; 地地点固定的代理点固定的代理。 它如同一个调停机构 , 协调移动用户和服务器之间的通信服务 ; 服务器服务器。当移动用户从一个地区到另一个地区时 , 它能选择一个合适的代理 , 实现与服务器和其它移动用户之间的通信。为了保证用户的合法接入和信息的安全传输 , 一般需要做到如

5、下 5 点：【1】访访问控制问控制。确保接入用户合法。此过程可以通过移动用户的 MAC 地址和用户的相关信息来实现。【2】身身份认证份认证。确保对方为其所声称的用户及数据的完整性 , 通过数字签名技术实现。【3】不不可否认性可否认性。确保其发出的信息事后无法抵赖 , 通过数字签名实现。【4】数数据完整性据完整性。防止信息被截获后数据被更改重新发送 , 通过消息认证码 ( MAC ) 和数字签名来实现。【5】保保密性密性。信息在传输中即使被截获 , 因截获者无法破解而毫无意义。通过数据的加密来实现。密码应用中常使用的两类椭圆曲线为定义在有限域 GF ( p ) 上的素曲线和在有限域 GF(2n

6、)上的二元曲线。素曲线计算不需素曲线计算不需二元曲线所要求的位位混淆运算混淆运算 , 对软件应用而言 , 最好使用素曲线最好使用素曲线 ;而对硬件应用对硬件应用而言 , 则最好使用二元曲线最好使用二元曲线 , 它可可用很用很少的门少的门电路来得到快速且功能强大的密码电路来得到快速且功能强大的密码体制体制 。p 椭圆曲线的加密和解密在 SEC1 的椭圆曲线密码标准 ( 草案 ) 中规定 , 一个椭圆曲线密码由下面的 6 元组所描述 :T = 式中 : p 为大于 3 的素数 , 它确定了 有 限 域GF ( p); a 和 b 确定了椭圆曲线 ; G 为循环子群 E 1的生成元 ; n 为素数且

7、为生成元 G 的阶 , G 和 n 确定了循环子群 E 1; h 为余因子 , 有 h = |E 1|/ n , h将交换群 E 和循环子群联系起来。用户的私钥定义为一个随机数 dd 0, 1, 2, , n - 1用户的公开密钥定义为 Q 点： Q = dG设要加密的明文数据为 M , 将 M 划分为一些较小的数据块 , M = m 1 , m 2 , , m t 。式中 : 0 mi n 。用户 A 将数据 mi 加密发送给 B , 加加密密过程过程如如下：下：【1】用户 A 查公钥库 PKDB, 查到用户 B 的公开密钥 QB 。【2】用户 A 选择一个随机数 dA , 且 dA 0,1

8、, 2, , n - 1 。【3】用户 A 计算点 X 1: (x 1 , y 1)=dAG 。【4】用户 A 计算点 X 2: (x 2 , y 2) =dAQB , 如果分量 x 2 = 0, 则转【2】。【5】用户 A 计算 C = mi x 2 mod n 。【6】用户 A 发送加密数据 ( X1 , C ) 给用户 B 。解解密过密过程：程：【1】B 用自己的私钥 dB 求出点 X2:dBX 1 = dB (dG) =dA(dBG) =dAQB = X2: (x2, y2)【2】对 C 解密 , 得到明文数据 m i = C x2-1 mod n 。与此类似 , 可以构造其他椭圆曲线

9、密码。环论和格论p环环 的的 基基 本本 定定 义义p整环整环p域域p格格 的的 基基 本本 定定 义义p分配格分配格p有界有界格格p补补格格p布尔代数布尔代数环环 的的 定定 义义：设有代数系统（，+，。），若满足以下条件：（）、（，+）为可换群；（即满足交换律、结合律、存在零元、负元）（）、（，。）为半群；（即满足结合律）（）、运算。对+满足分配律，即对任意，存在。（。（+ +）。）。+ +。（+ +）。）。+ +。整整 环：环： （，+，。）为环，它有单位元素且是可换环，无零因子，则称（，+，。）是一个整环整环。域域：设环（，+，。）满足下列条件：（1）、R至少有两个元素（2）、（R，。

10、）有单位元素（3）、（R，。）是可换的（4）、除零元外，其余元素均存在逆元素（aR的逆元可记作a-1）环论在计算机领域的应用：环论在计算机领域的应用：（）、广义圆环论在可持续发展中广义圆环论在可持续发展中的应用的应用（）、环论在线性代数中的一些应环论在线性代数中的一些应用用 （）、一个基于广义圆环论的系统一个基于广义圆环论的系统管理数字化模型管理数字化模型p广义圆环论在可持续发展中的应用广义圆环论在可持续发展中的应用 【摘要摘要】从世界经济全球化、入关和西部大开发出发 ,以辩证法为指导 ,数学为工具 ,用泛系方法研究可持续发展。提出广义圆环论 ,建立数学模型 ,给出四种基本类型。以绿化植树造林

11、工程为例。说明它在规划、预决策、管理方面的应用p环论在线性代数中的一些应环论在线性代数中的一些应用用 【摘要摘要】：把经典环论中的一些重要结论应用到线性代数中矩阵的研究,通过幂等矩阵和可逆矩阵给出方块矩阵新的分解,并讨论一般矩阵的相关性质.p一个基于广义圆环论的系统管理数字一个基于广义圆环论的系统管理数字化模化模型型p【摘要摘要】：从一般系统观点出发, 利用以闭环系统和圆环论为基础的广义圆环论构建了一个分布式网络考试管理系统p模型 中小学教师现代教育技术培训考试信息处理系统一个基于广义圆环论的系统管理数字化模型域在计算机领域的应用：域在计算机领域的应用：（）、近冰梅近冰梅类域类域论论（）、二次

12、域理想类数生成元的求解及计二次域理想类数生成元的求解及计算机实现算机实现（）、基于半邻域法的自适应图像边缘提基于半邻域法的自适应图像边缘提取方法取方法p 近冰梅近冰梅类域类域论论 【摘要摘要】：正类域论(Class Field Theory)是数学诸理论中,体系最完美的一种数学百科全书如是说。她是现代数论的一门极重要理论,现在已渗透应用到各分枝,几乎无处不涉及。此理论由希尔波特(Hilbert)在1900年左右猜测出,主要由福特汪格勒(Furtwangler),高木贞治(Takagi),阿廷(Artin)至1927年给出证明。但象“类域构作”这样的世纪性大问题,研究还远无尽头,是现代最激烈前沿

13、之一。类域论理论系统深邃,定理异常丰富,初学者短期内不易掌握。p二次域理想类数生成元的求解及计算机实二次域理想类数生成元的求解及计算机实现现 【摘要摘要】二次域上的理想类数是有限的,文章利用理想类、类群的相关性质,通过计算机编程,求解出二次域Z(D)的类数及理想的代表。p 基于半邻域法的自适应图像边缘提取方法基于半邻域法的自适应图像边缘提取方法 【摘要摘要】：图像边缘对图像识别和计算机分析十分重要,至今已经提出了大量的各种类型边缘提取算法.该文在半邻域法的基础上提出了一种基于自适应阈值选择的图像边缘提取算法,在判断某一像素点是否在边缘上时,以该像素点为中心,选取33的区域为研究对象,求出该区域

14、的最大、最小、均值像素值及标准差,在选用标准差为其阈值的同时,还考虑人的视觉对于灰度分辨能力的限制.最后,对多幅灰色图像进行了边缘提取,结果证实了该文方法的有效性.p半半邻域法邻域法采用半邻域法检测某一像素点是否在边缘上 ,是对其周围相邻的 8 个像素点进行分析 , 把它们划分为两组,按照顺时针方向 ,以连续 3个像素点为一组 ,其余的 5 个像素点为第二组 . 这样就有 8 种情况 ,如图 1 所示( 表示被检测像素点 , 表示第一组像素点, 表示第二组像素点) . 令 N 为中心点 的 8 邻点集合 , N 为N 集的灰度均值, M3 为 N 中 3个连续邻点的集合 , M3 为 M 3集

15、的灰度均值 , M5 为 N 中 5 个连续邻点的集合 ,M5 为 M5 集的灰度均值 . f( i , j) 表示第(i ,j) 个像素点的灰度值, T 表示所给的阈值 . 具体的实现步骤为 :( 1) 首先在这 8 种情况之中, 选取一组 , 使得M5 - M3 的值最大 , 这是边界最可能出现的一种组合 ;( 2) 选取一个阈值 T ,按照下面公式判断 :f( i ,j)= N , | M5 - M3 | max T , 边界不明显 ；（1） M5 , | M5 - M3 | max T , 边界明显； （2） 另外,在文献 7 中给出了一种简便的算法 , 先对周围的 8像素点的像素值进

16、行大小排序, 将像素值大的5 个组成 M5 集 ,较小的 3 个组成 M3 集, 求出这两组的均值 ,再用均值差和给定的阈值 T 作比较,如果大于 T ,则判为边缘上的点, 反之不是边缘点. 半邻域算法虽能够保护边界,但提取的好坏跟给定的 T 值相关很大 ,所以受到一定的限制.本文算本文算法法本文算法是在半邻域的基础上, 采用一种自适应的阈值选择法, 选用 33 的区域为研究对象 , 计算出其最大、 最小的像素值及标准差,选择标准差为阈值 T 的同时 , 还考虑人眼对灰度分辩能力的限制. 这样既克服了半邻域法选择阈值 T 的困难 , 又可以避免一些虚假边缘的检测, 从而能有效地提取图像的边缘

17、.算法见pdf文件格格 论论：L为非空集合，+和。是L上的两个二院运算，如果他们满足交换律、结合律、吸收律，则代数系统（L,+,。）为格，也称作代数格。交交换换律：律：a+b=b+a，a。b=b。a结合律：结合律：(a+b)+c=a+(b+c)， (a。b)。c=a。(b。c)吸吸收收律：律：a+ (a。b)=a，a。(a+b)=a分分 配配 格格：如果格（L，+，。）满足分配律，即对任意a,b,c,L，有：a+(b。c)=(a+b)。(a+c)a。(b+c)=(a+b)。(a+c)则称（L，+，。）是分配格。有有 界界 格格：设格（L，+，。）中的+有单位元素1及。有单位元素0，即对aL有a

18、+1=a，a。0=a，则称该格为有界格格论在计算机领域的应用：格论在计算机领域的应用： （）、基于格论的哈希函数在数据查询基于格论的哈希函数在数据查询认证中认证中的的 应应用方案用方案 （）、基于格论的基于格论的GNSS模糊度解算模糊度解算 （）、基于格论和基于格论和TRIZ技术进化理论的理想技术进化理论的理想化化水水平表述方式平表述方式p基于格论的哈希函数在数据查询认证中的应用基于格论的哈希函数在数据查询认证中的应用方方案案 【摘要】：数据查询认证是保证信息安全的关键技术。基于格论的哈希函数解决了传统哈希函数易受到攻击的问题,增强了其抗碰撞性。本文将基于格论的哈希函数应用到数据查询认证过程之

19、中,阐述如何将基于格论的哈希函数和格摘要的思想应用到各实体运行算法之中,阐述其实体构成,描述实体间的通信协议,并对实体的空间和时间复杂度进行详细分析。经对比,该方案明显降低了数据查询认证过程的复杂度。p基于格论的基于格论的GNSSGNSS模糊度解算模糊度解算 【摘要】：快速、准确地解算整周模糊度是实现GNSS载波相位实时高精度定位的关键,由于模糊度之间的强相关,基于整数最小二乘估计准则时,需要较长的时间才能搜索出最优的整周模糊度向量。为了提高模糊度的搜索效率,本文在扼要介绍格论的理论框架基础上,引入基于格论的模糊度解算方法,通过格基规约来降低模糊度之间的相关性,从而快速搜索出最优的整数模糊度向

20、量。与此同时,将GNSS领域的主要降相关方法统一到格论框架下,探讨了并建议采用Boot-strapping成功率作为格基规约的性能指标之一。最后试验分析三频多系统长基线相对定位情况下,不同格基规约可获得的性能。p基于格论和基于格论和TRIZ技术进化理论的理想化水平表技术进化理论的理想化水平表述方述方式式 【摘要】：现有的技术理想化水平定义公式存在不易测算、难于比较折衷以及无法与TRIZ技术进化理论有效对接的缺陷。为解决上述问题,构造了一种基于格论的新型技术系统理想化水平表述方式,并结合Hasse图对技术进化过程中的理想化水平变化程度进行了分析。研究发现,某些技术系统之间存在理想度不可比性特征以

21、及理想度评判的参考点效应,且新型理想化水平表述方式可较好地表征和解释技术系统迂回进化和理想化水平非连续变化的特征。p 基于格论的技术系统理想化水平表述方基于格论的技术系统理想化水平表述方式式评判技术系统状态的理想化水平，本质上就是对技术系统按照有用功能、成本和耗费、有害功能三类指标进行排序。因此，可以构建一个相应的由 n 维变量元素(x1,x2 ,x n )组成的集合 I 进行排序， 以反映其理想化水平高低。然而由于技术系统有用功能是正向指标，而成本和耗费、有害功能是负向指标，因此可以先将二者的所有量值按取相反数的方法正向化，从而得到一个如下 n 维变量元素构造方式：(x1,x2, ,xn1,

22、xn1+1,xn1+2, ,xn2)(2)在式(2)中： x i 0，+)，i1，2，n1 x j (-，0，jn1+1，n1+2，n2式(2)表示可以用 n2个指标综合评价技术系统的理想化水平。在这 n2 个指标中，描述技术系统有用功能的指标共有 n 1 个，这些指标的取值范围是非负实数集，当某个指标值取零值时，则表示技术系统暂时未能获得该项有用功能；描述技术系统成本耗费和有害作用的指标共有 n2 -n1 个， 这些指标的取值范围为非正实数集，某个指标值取负表示技术系统存在该类成本耗费或有害作用，取零则表示该类成本耗费或有害作用不存在或已被有效消除。在实际使用过程中，x i 、x j 的参量名称与属性根据不同技术系统的特性决定。基于格论的技术系统理想化水平表述方式格论中的布尔代数布布 尔尔 代代 数数：代数系统（B，+，。）只要满足交换律、分配律、同一律和互补律，则称它为布尔代数l 在布尔代数中，元素a的补元素可以认为对a的一元运算，因此布尔代数（B，+，。）也可以写作（B，+，。，-），表示它是由两个二元运算及一个二元运算所组成的代数系统。格论中布尔代数在计算机领域的应用：格论中布尔代数在计算机领域的应用：（）、基于布尔代数的木马行为界定及判基于布尔代数的木马行为界定及判别别（）、泛布尔代数在数字逻辑电路设计泛布尔