数据加密技术（代数系统1）课件.ppt

《数据加密技术（代数系统1）课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1代数系统的定义集合的性质：确定性，互异性和无序性。定义1n元运算:设S是一个非空集合，函数f：Sn→S称为S上的一个n元运算，n称为运算f的阶数（注意：封闭性！）。例1(1)加法、乘法运算是自然数集N、整数集Z、有理数集Q、实数集R上的二元运算。(2)非0实数集R－{0}上的乘法、除法运算是R－{0}上的二元运算。但加法、减法不是，因为加法、减法运算得到的结果0不在集合R－{0}中，因而对于加法和减法运算封闭性不成立。例2设Zm＝{[0]，[1]，…，[m－1]}是模m同余关系所有剩余类组成的集合，在Zm上定义运算＋

2、m和×m为（封闭性）：对任意的[a]、[b]∈Zm，[a]＋m[b]＝[a＋b]，[a]×m[b]＝[a×b]，则＋m和×m是Zm上的二元运算。＋m0123401234012341234023401401240123当S为有限集合时，S上的二元运算可以列表给出，称其为S关于该运算的运算表。设S＝{a1，a2，…，an}，*是S上的二元运算，则S的运算表如下表所示:定义2一个非空集合S连同若干个定义在S上的运算f1、f2、…、fm组成的系统称为代数系统或代数结构，记作。集合S的基数称为代数系统

3、的基数。由定义可知，一个代数系统需满足以下3个条件：(1)有一个非空集合S。(2)有建立在S上的一些运算。(3)这些运算在S上是封闭的。1.单位元定义3设代数系统，且存在el、er、e∈S，对任意x∈S，若el*x＝x，则称el是S中关于*的一个左幺元；若x*er＝x，则称er是S中关于*的一个右幺元。若e关于*既是左幺元又是右幺元，则称e为S中关于*的幺元（单位元）。例3(1)在中，运算＋的幺元是0，运算×的幺元是1，因为x＋0＝0＋x＝x，x×1＝1×x＝x。(2)在中，

4、运算＋m的幺元是[0]，运算×m的幺元是[1]。+01010110×01010001+01201201220201×012012000012021例4设S＝{a，b，c，d}，在S上定义运算*和如下表所示，试指出关于*和的左幺元或右幺元。解b、d是S中关于*的左幺元，关于*没有右幺元；a是S中关于的右幺元，关于没有左幺元。定理1设是一个代数系统，el、er分别为S中关于*的左幺元和右幺元，则有el＝er＝e，且e是S中关于*的惟一的幺元。2.零元定义4设代数系统

5、>，且存在l、r、∈S，对任意的x∈S，若l*x＝l，则称l是S中关于*的一个左零元；若x*r＝r，则称r是S中关于*的一个右零元。若关于*既是左零元又是右零元，则称为S中关于*的零元。例5(1)在中，[0]是零元，因为对任意的[a]∈Zm，有[a]×m[0]＝[0]×m[a]＝[0]。定理2设是一个代数系统，l、r分别为*的左零元和右零元，则有l＝r＝且是S上关于*的惟一的零元。3.逆元定义5设是一个代数系统，e是S中关于*的幺元。对于x∈S，若存在

6、yl∈S使得yl*x＝e，则称yl是x的左逆元；对于x∈S，若存在yr∈S使得x*yr＝e，则称yr是x的右逆元。对于x∈S，若存在y∈S既是x的左逆元又是x的右逆元，则称y为x的逆元，通常记为x－1。例7设S＝{a，b，c，d}，S上定义运算*和如下表所示，试讨论关于运算*、在S上的特殊元素。解对于运算*，无幺元也无零元。对于运算，a是幺元，由运算表可知，a－1＝a，b－1＝d，c－1＝c，d－1＝b，对于运算无零元。例8设S＝{a，b，c}，且对任意的x、y∈S有x*y＝x。列出运算表，并判断*的性质和相应

7、的特殊元素。解运算表如下表所示由运算表可知：*是封闭的；*是不可交换的，因为运算表不对称；a、b、c是关于*的右幺元，但无左幺元；a、b、c是关于*的左零元，但无右零元。2半群和独异点2.1半群定义6设是一个代数系统，其中*是S上的二元运算，若*满足结合律，则称为半群。若*还满足交换律，则称为可交换半群。例1代数系统，、、都是半群，且是可交换半群。例2设S是一个非空集合，对于任意的a、b∈S，规定a*b＝b，试说明构成半群。解由a*b＝b可

8、知，*在S上是封闭的。又(a*b)*c＝c＝b*c＝a*(b*c)，于是*满足结合律，所以是一个半群。定义7设是一个半群，T是S的一个非空子集且*在T上是封闭的，则称为的子半群。例3设是一个半群，a∈S，M＝{an

9、n∈N}，则是的子半群。证明因为是半