（基础数学专业论文）密码群并半群上的中心同余.pdf

西南大学硕士学位论文中文摘要 密码群并半群上的中心同余 学科专业：基础数学研究方向：半群代数学 指导教师：郭聿琦教授硕士研究生：冯建( $ 2 0 0 7 3 1 4 0 ) 摘要 f r e e s e 和m c k e n z i e 介绍了代数中心的概念，并指出它是该代数上的一个同余 现已知在这个意义下，一个群的中，5 - 恰与通常意义下群的中心所确定的等价关系 一致在这本文中，我们将考察一半群的中一5 - 特别地，我们刻画了一些密码群并 半群的中心 关键词：中心；同余；密码群并半群；完全单半群 西南大学硕士学位论文 英文摘要 t h ec e n t e rc o n g r u e n c e so nc r y p t o g r o u p s t h ec e n t e ro fa na l g e b r a ，w h i c hi sac o n g r u e n c eo nt h i sa l g c b r a ，w a si n t r o d u c e db y f r e e s ea n dm c k e n z i e i ti sw e l lk n o w nt h a tt h ec e n t e ro fag r o u pi nt h i ss e n s ec o i n c i d e s w i t ht h ee q u i v a l e n c ed e t e r m i n e db yt h eu s u a lc e n t e ro ft h i sg r o u p i nt h i sp a p e r ，w e i n v e s t i g a t et h ec e n t e ro fas e m i g r o u p i np a r t i c u l a r ，w ec h a r a c t e r i z et h ec e n t e ro fs o m e k i n d so fc y r p t o g r o u p k e y w o r d s ：c e n t e r ；c o n g r u e n c e ；c r y p t o g r o u p ；c o m p l e t e l ys i m p l es e m i g r o u p i i 独创性声明 本人提交的学位论文是在导师指导下进行的研究工作及取得的 研究成果。论文中引用他人已经发表或出版过的研究成果，文中已加 了特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同 仁在文中作了明确说明并表示衷心感谢。 学位论文作者：冯走签字日期：如口年争月 1 3 日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院( 筹) 可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 。 学位论文作者签名：吗建 签字日期：剜d 年分月j 3 日 西南大学硕士学位论文前言 第一章前言 。半群代数理论”在数学内部( 组合数学，图论，符号动力学) 和外部( 理论计 算机科学，信息科学，生物技术等) 的推动下，系统的研究了六十余年，已形成为代 数学中的一个研究对象，研究课题到研究方法都颇具特色的独立的学科分支，它 与“群论”的关系类似于“环论”与“域论”的关系( 在m a t h e m a t i c a lr e n e w s 的 s u b j e c tc l a s s i f i c a t i o n 里，。半群( 2 0 m ) ”归于。群论( 2 0 ) ”是历史的惯性所致) ，是 一个有着宽广背景和应用背景的基础学科，其研究在国际上方兴未艾 半群的同余理论是半群研究的一个重要内容，根据一种定义方式下的同余在 不同半群上的具体性质及表现形式可以对半群做一定程度上的分类再者，对半 群自身的不同同余的研究也有利于对该半群自身结构的把握目前，完全正则半 群的同余理论已经趋于成熟，特别地，密码群并半群这一特殊的完全正则半群上 的同余更是得到充分的刻画然而，对半群上某些同余的具体刻画却研究的不是 很充分 文献【1 】对一般的代数定义了中心同余这一概念我们知道，半群是一种重要 的2 代数然而，半群的中心却长期未引起半群工作者的注意，在现有文献中鲜 有研究结果本文就半群这种2 代数的中心展开研究，我们给出了一般半群上中 ，5 - 同余较具体的刻画同时，借助文献【2 】【3 】和【4 】中的一些性质及结构定理，我们 给出了几种类型的密码群并半群上中心同余的具体的刻画 1 西南大学硕士学位论文文献综述 第二章文献综述 在文献1 中定义了代数的中心同余这一概念现将代数具体为半群时中心 同余的概念给出 设s 是一半群。定义s 上的二元关系如下： ( a ，b ) z ( s ) = 争 ( v 佗n ，c l ，c 忭，d 1 ，厶s ，w ( x ，y t ，y n ) j k ) ( o ，c l ，c n ) = 伽( 口，d l ，如) 铮w ( b ，c l ，c n ) = 叫( 6 ，d l ，如) 】 则称z ( s ) 为半群s 上的中心 同时，文献 1 】也保证了上述定义的中心z ( s ) 是同余，进而我们称其为中心 同余在【1 】1 中讨论了当代数是群，环时，中心同余z ( s ) 的具体表现形式为此，半 群的中心同余又有何表现形式呢? 也会像群，环那样具有很好的对应和表现形式 吗? 经过本文的研究对一般半群而言，上述定义的中心同余可简化为 ( o ，6 ) z ( s ) 毒= 争( v m ，仇7 ，礼，n s 1 ) i m a m 7 = n a n 咎m b m 7 = n b n 7 】， 且其中( mgs 或ngs ) 【m = 1 ，n = 1 】，( 7 7 7 , gs 或礼gs ) 【m 7 = 1 ，t 1 , = 1 】这一改 进在形式上有了很大的简化，但仍不能反映该同余与半群内部结构的关系于是， 在文献【2 】 3 】，【4 已知的一些重要且基础的半群结构的前提下，本文对这些半群的 中心同余作了进一步反映结构关系的刻画 2 西南大学硕士学位论文 第2 章预备知识 第三章预备知识 设s 是一个非空集合称有序对( s ) 为个半群，如果s 上的二元运算。” 满足结合律 ( v a ，b ，c | s ) ( n b ) c = a - ( b c ) 】 1 s 称为s 的幺元或单位元，若 ( v s s ) 1 s = s l = s 】 此时，称半群s 为幺半群 称半群s 中元素a 为正则元，如果存在x s 使得a x o , = a 称半群s 为一正 则半群，如果s 中任何元素都是正则元称a 是a 的逆元，如果a a a = a ，a a a 7 = a 称s 中满足a 2 = a 的元素a 为幂等元记s 中的全体幂等元构成的集合为e ( s ) 每个元素都是幂等元的半群称为带交换的带称为半格如果s 满足关于任意 a ，b s a b = a ，则称s 是一左零半群对偶地，有右零半群的概念设，a 为非空 集合，在ixa 上定义运算如下 ( v 0 ，久) ，d ，p ) i a ) 【0 ，入) u ，p ) = ( i ，p ) 】， 则称i a 连同以上运算形成的半群为矩形带 称s 上的二元关系0 为一等价关系，如果 ( a ) ( v a s ) ( 口，a ) 拶； ( b ) ( v a ，b s ) ( o ，b ) 0 哥( b ，a ) 口】； ( c ) ( v a ，b ，c s ) ( n ，b ) 口，( b ，c ) p 考( a ，c ) 刎 称上述等价关系口为s 上的同余，如果口满足如下相容性 ( v ( 8 ，b ) p ，v c s ) ( 口c b c ) 9 ，( c a ，c b ) 刎 称s 上的二元关系“”是偏序关系，如果 ( a ) ( v a s ) ( 口，o ) ； ( ) ( v a ，b s ) 【( d ，b ) 号( b ，o ) 】； ( c ) ( v a ，b ，c s ) 【( o ，b ) ，( b ，c ) = = ( a ，c ) 】 在半群s 上定义二元关系2 ，留如下：关于任意a ，b s ， a w b 牟冷s 1 a = s 1 b n 留6 褂a s l = b s l 它们显然均是s 上的等价关系，记澎= 髟n 露且9 = 2v 留 3 西南大学硕士学位论文第2 章预备知识 设g 为一群，a 为非空集合，p ：a ，叶g 为一映射( 称其为夹心阵) ，其 中，( 入，i ) p = p x i ( 也称p m 为p 中的元素) 在s = i g a 上定义如下运算：关 于任意( t ，g ，入) ，( 歹，庇，p ) s ，( i ，g ，入) ( h ，p ) = ( i ，g p x j h ，肛) 称s 关于该运算形成的 半群为群g 上的r e e s 矩阵半群记作( j ，g ，a ；p ) 称同构与该类半群的半群 为完全单半群 称半群s 为一完全正则半群，如果关于任意a s ，存在a - 1 s 使得 a = a a 1 a ，( n 一1 ) 一1 = a ，a a 一1 = o 一1 a 完全正则半群也称为群并半群称完全正贝4 半群是纯正的，如果e ( s ) 形成s 的 子半群称完全正则半群s 是密码的，如果( n 砷o = ( a o b o ) o ，其中，a o 是玩中的幂 等元 设y 是一半格， & i 口y 】是一族两两不交的半群关于任意a ，卢y 2 p ) ，札，声：_ & 是一同态假设以下条件也满足：关于任意a ，p ，7 r ( a p 7 ) ， ( 1 ) 妒a 口是& 上的恒等映射， ( 2 ) 九，口如，1 = 九 在s = u 口y 上定义运算”o ”如下：关于任意a ，p y , a & ，b 昂， aob = ( a c a ，。口) ( 劬卢，卵) 则( s ，o ) 是一半群，称其为半群族 & l 口y ) 的强半格记作【y ；s a ，丸，别称s 是c l i f f o r d 半群，如果s 是群的强半格称| s 是一正规密码群并半群，如果s 是 完全单半群的强半格 设s 是一半群定义s 上的二元关系如下： ( a ，b ) z ( s ) = 争 一佗n ，a l ，c 。，d l ，如s ，叫( z ，y t ，y n ) j x ) 陋( 口，c l ，a n ) = w ( a ，d l ，如) 铮叫( 6 ，c 1 ，a n ) = t ，( 6 ，d t ，如) 】) 则称z ( s ) 为半群s 上的中心由文献 1 知如此定义的中心z ( s ) 是同余，进而称 其为中心同余 未作说明的其他符号可参见文献【1 】【2 】和【3 】 4 西南大学硕士学位论文 半群上的中心同余 第四章半群上的中心同余 本章对半群的中心同余展开系统的研究我们给出了半群上中心同余的具体 刻画特别地，借助文献【2 】， 3 ，【4 】，我们刻画了密码群并半群上的中心同余 4 1 半群的中心同余 设x 为非空变元集，取为x 上的自由幺半群叉设s 为半群，关于任意 a l ，a 2 ，a n s ，w ( x l ，z 2 ，x 竹) j x ，w ( a t ，a 2 ，一，a 1 ) 是在w ( x l ，x 2 ，x n ) 中 依次将x l ，x 2 ，替换为n - ，a 2 ，a n 并按s 中的运算得到的s 中的元在s 上定义如下的二元关系： ( a ，b ) z ( s ) = 争 ( v 仃n ，c l ，c 。，d 1 ，锄s 叫( z ，! ，1 ，y n ) f x ) ( o ，c l ，c n ) = 伽( d ，d t ，厶) 铮w ( b ，c l ，c n ) = w ( b ，d l ，如) 】) 在自由幺半群取中，钳( z ，y l ，y n ) f x 一般可用如下形式表示： 伽( z ，y l ，可n ) = z h u l ( m ，弘n ) 。2 u 2 ( 秽1 ，) z 2 m 一1 u r n 一1 ( 可l ，y n ) x 2 仇( 1 ) 其中k o ，i = 2 ，仇一l ，b o ，j = 1 ，m ，当幻= 0 时，幽= 1 ，1 表示取中 的幺元当s 为群时，由文献 1 1 知z ( s ) = ( 9 ，h ) sxs ：g h 一1 c ( s ) ) ，其中 c ( s ) = n s ：( s ) a 8 = s a 定理4 1 1设s 是一半群则 ( o ，6 ) z ( s ) = 争( v m ，m 7 ，礼，礼s 1 ) i m a m 7 = n a n m b m = n b n 】， 其中( m 粤s 或ngs ) m = 1 ，n = 1 1 ，( m gs 或礼gs ) 【m 7 = 1 ，n = 1 】 证明必要性关于任意( a ，b ) z ( s ) ，分别取 ( z ，耖1 ，y 2 ) 2y l z y 2 ，y l x ，x y 2 ， 即得 充分性记由定理中陈述之条件确定的s 上的二元关系为p 容易验证，p 为 s 上的同余于是 ( 口，b ) p = = 争( 口。，b 。) p ，( j n + ) 5 西南大学硕士学位论文 半群上的中心同余 关于任意c 1 ，c n ，d l ，如s ，伽( z ，y t ，y n ) f x ， 伽( 口，? ) = t t ，( o ，d ) 错 = 辛 因此( a ，b ) z ( s ) - u 1 ( - 才) a 1 2 札2 ( - c - # ) ，口l m l u m l ( 7 ) o k ：a l - u l ( 孑) 口f 2 u 2 ( 了) ，a i m 一- 一1 ( j ) 。l m ( 据( 1 ) ) b l , 让1 ( ? ) o 。2 u 2 ( 吉) ，a i m 一1 u m l ( 孑) n 。m = 砂t u l ( 孑) 8 f 。u 2 ( j ) ，口k 一- 一l ( 言) a k ( 据定理条件) 护- u 1 ( 暑) 矽：u 2 ( 暑) ，6 l m 一u m 一1 ( 言) o m = b h 札1 ( uj v l 。抛( 孑) ，砂一u m 一1 ( 才) 。k ( 据定理条件) 铮 扩- u l ( 7 ) b z z u 2 ( 言) ，6 l m 一- t 厶m l ( 才) 护m ：咖u 1 ( 孑) 6 f 。缸2 ( 言) ，护m 一- 一1 ( j ) 咖( 据定理条件) 钳 加( 6 ，7 ) ：叫( 6 ，言) 6 口 西南大学硕士学位论文 半群上的中心同余 4 2 关于完全单半群的中心同余 设s = ( j ，g ，a ；p ) 是以。为单位元的群g 上的r e e s 矩阵半群，b = i a 是矩形带，a = ( 1 ，a ) ，b = ( 歹，p ) b ，g ，h g 在文章中，s 中的元素( i ，g ，入) ，( ，h ，p ) 分别记为( n ，g ) ，( 6 ， ) ，夹心矩阵p = p m ) 中的元素p 沁记为p a 进而s 中的运算 可用以下形式给出 ( v ( a ，9 ) ，( b ，h ) s ) 【( n ，9 ) ( 6 ，h ) = ( a b ，g p 种) 1 同时将s 改记为s = 旧，g ；p ) 。夹心矩阵p 在鑫处被正规化【3 ，定义i i i3 2 。5 】， 如果 ( v b b ) p b a = p a b = 。 ( 3 ) 设s = ( b ，g ；科，其中p 在鑫b 处被正规化。称( 负n ) e q ( b ) n ( g ) 是容 许的，如果 ( v a ，b b ) a s b 哥( v c b ) p a c p b c l n ，p c a p 五b 1 ， ( 4 ) 其中e q ( b ) 是b 上的所有等价关系构成的集合，n ( c ) 是g 的所有正规子群构成 的集合s 上的二元关系 p = 觚) = ( ( o ，9 ) ，( 玩九) ) s s ：a s b ，g h 。1 ( 5 ) 是s 上的同余 3 ，引理i i i3 4 4 1 引理4 2 1 设s = ( 口，g ；p ) ，其中p 在鑫b 处被正规化若( 口，c ( g ) ) e q ( b ) ( g ) ，其中 a o b 令( v c b ) p a c = p b c ，p = p c b ， 则( 9 ，c ( g ) ) 是容许的，进而p ( o ，c ( g ) ) 是s 上的同余 证明由( 4 ) ，( 5 ) 易知 定理4 2 2 设s = ( b ，g ；p ) ，其中p 在a b 处被正规化则 z ( s ) = p ( e ，c ( g ) ) ， 其中p ( e ，c ( g ) ) 如引理4 2 1 所述 证明 任取( ( o ，9 ) ，( 6 ， ) ) p ( p ，c ( g ) ) 关于任意晓= ，9 1 ) ，m = ( m ，g i ) ，壳= 7 西南大学硕士学位论文 半群上的中心同余 ( n ，9 2 ) ，磊= ( n ，炙) s ，有 ( m ，9 1 ) ( o ，夕) ( m ，g ：) = ( 礼，卯) ( 口，9 ) ( n 7 ，9 1 ) 镑 净 考 哥 = = ( m o m ，9 1 p d m 卯m ，砌9 i ) = ( n a n ，9 2 p a n g p n 。磊) ( 据( 2 ) ) ( m 6 口n ，9 1 2 k m ( 9 危一1 ) ，i 砖n ，m 9 i ) = ( n b n ，9 2 p a n ( g h - 1 ) ，。建) ( b 为矩形带) ( m b r a 7 ，( g h 一1 ) 9 1 p 概坳。，棚：) = ( n b n ，( g h 。1 ) 9 2 p b a h p n , 。b g 2 ) ( 据引理4 2 1 ) ( m 6 m ，9 1 p h 坳m ，m g i ) = ( n l r a ，9 2 p h h p n n b 磊) ( m ，9 1 ) ( b ， ) ( m ，9 i ) = ( 几，9 2 ) ( b ， ) ( n ，如) ， 类似可证m = 矗：1 s 1 ，及疵= 蠢7 = 1 s 1 的情况因此由定理4 1 1 知 p ( o ，g ( g ) ) 冬z ( s ) 下证z ( s ) p ( o ，e ( g ) ) 任取( ( n ，夕) ，( 6 ，危) ) z ( s ) 则关于任意k g ，有 ( & ，g 一1 ) ( 口，9 ) ( a ，k ) = ( a ，七) ( o ，9 ) ( 鑫，g 一1 ) = ( 鑫，免) ( 据( 2 ) 和( 3 ) ) ， 进而 ( a ，g 一1 ) ( 6 ， ) ( 鑫，七) = ( 鑫，奄) ( 6 ，危) ( a ，g 一1 ) ， 即 ( 鑫，g 一1 九七) = ( 鑫，k h g 一1 ) 由k 的任意性，特别取后= “可得g h 一1 = h g ，因此g h - 1 c ( g ) 又因为关于任 意c b ， ( a ，b ) ( 口，9 ) ( & ，) = ( a ，g ) ( 据( 2 ) 和( 3 ) ) ， ( a ，l ) ( o ，9 ) ( c a ，p 羞) = ( 鑫口施，p 蕊僦鑫拶= ) = ( a ，9 ) 因此 ( 鑫，) ( 6 ，危) ( a ，。) = ( 鑫，) ( 6 ， ) ( c & ，p 2 ) ， 从而 ( a ，h ) = ( 龟却曲耐) 故p c b = 融同理可得p b c = 口 设s = ( b ，g ；p ) ，其中p 在a b 处被正规化由( 4 ) ，( 5 ) 易知p ( 。，c ( g ) ) ，p ( e ， 。 ) 是s 上的同余，且由( 【3 】，引理i i i 4 1 0 ) 知 p ( e ，g ( g ) ) = p ( e ，e ( g ) ) vp ( o ， ) ， 其中是b 上的相等关系，0 如引理4 2 1 所述而据文献 3 】中的i i i 4 1 2 ，p ( e ，c ( g ) ) 是s 上的一个幂等元分离同余，p ( e ，是s 上的最大幂等元纯同余 8 西南大学硕士学位论文 半群上的中心同余 有 定理4 2 3 设s = ( b ，g ；p ) ，其中p 在a b 处被正规化则 反。，c ( g ) ) = ( a ，6 ) s s ：( s ) a 童b = 6 a ) 。 证明 记该定理中等式右边所确定的s 上的二元关系为p 若( ( o ，g ) ，( 6 ， ) ) p ( 。，e ( g ) ) ，则n = 6 ，g h 一1 c ( g ) ，且关于任意= ( 3 ，七) s ， = ( a s a ，g p s 。慨h ) = ( a ，g h 一h p 船k p a 。h ) = ( a ， 乳口口p 。9 矗一1 h ) ( 据g h 一1 c ( a ) ) = ( a ，危) ( s ，后) ( o ，g ) 故j d ( 。，e ( g ) ) p 若( ( n ，夕) ，( b ， ) ) p ，吾= ( a ，k ) s ，贝0 ( 口，9 ) ( & ，老) ( 6 ，h ) = ( b ，尼) ，七) ( 口，g ) = 净( 口铀，g p a d k p b a a h ) = ( b & a ，h p s b k p 粕g ) ( 据( 2 ) ) 哥( a b ，g k h ) = ( b a ，h k g ) ( 据( 3 ) 及b 是矩形带) = 辛a = 6 ，g h 以c ( c ) ( 据b 是矩形带及k 的任意性) 故p p ( e ，c ( g ) ) 9 口 西南大学硕士学位论文半群上的中心同余 4 3 关于密码群并半群的中心同余 设s = ( i s , & ) 是完全正则半群称s 是密码群并半群，如果澎是s 上的同 余称密码群并半群s 是正规的，如果酬澎是正规带，也即，s 是完全单半群的 强半格，通常记为s = 【y ；，x 口，口】称密码群并半群s 是纯正的，如果s 的幂等 元集e ( s ) 是一个带( 见文献 3 】) 。 引理4 3 1 ( 【3 】，引理i i 4 7 )设s = ) 是完全正则半群，p 够( s ) 若a ，p k 口2p ，o ，c & ，b & ，( o ，6 ) p ，则存在d 昂，使得( c ，奶p 且d c 引理4 3 2 设s = ( t t , ) 是完全正则半群则z ( s ) 勿 证明设o & ，b 岛，o t ，p y 则 ( o ，b ) z ( s ) = = = 争( o n 一1 ，6 0 一1 ) z ( s ) = = 争( o o ，b a 一1 ) z ( s ) ， 其中伍o & ，b a 一1 & 芦，q2n p 由引理4 2 1 知，存在c 跏，使得c n o ，( 扩，c ) z ( s ) ，且易知此时c = c o ，故( 0 0 ，c o ) z ( s ) 又因为 c o o o = c o c o 哥0 0 口0 = 0 0 c o 看a 0 = c o & 口( 据定理4 1 1 ) ， 所以口p = n 同理司证a p = p 口 引理4 1 3 3 ( 【4 】，定理1 )设b = ( i i , 风) 是带，其中y 是半格关于任 意o t y ，设= j e t ( 风，g n ；圪) 是以坛为单位元的群g n 上的r e e s 矩阵半群， 且夹心阵最于a 现处被正规化记u 。，p ( 口) = p o a 硒p & 诫l a ，口( o ) 2p 。- i 。 a 。， 其中口，p i s , a p ，n 吼关于任意a ，p r o l 卢，设o a 目是从g a 到g 口 的同态且满足以下条件，关于任意q 屈，y a p 7 ：( i ) 儿，n = l c 。；( i i ) 氏，卢郎，7 = 如，1 缸。( 鑫蘼) ，其中e 9 表示g 上的内自同构；( i i i ) ( v 0 鼠。) p n 既，p = ，筘( 8 ) 玩菇，声( 8 ) ；( i v ) ( v b ，c 玩，z = ( 口，9 ) & ) 喊勐z ，芦= z ，锣画p 咖， 其中z 盯口，芦= u p ( n ) ( 9 气，卢) ，p ( n ) 关于任意z = ( n ，9 ) & ，妙= ( b ，h ) 昂，在 s = u a y & 上定义运算如下： z 木掣= ( a b ，( z ，邱) p 晶玉口( 岁盯反祁) ) ， ( 6 ) 则s 是密码群并半群反之，每一个密码群并半群均可如此构造 设s = 似) 是密码群并半群，b = 既) 如引理4 3 3 所述，& 是r e e s 矩 阵半群，( u q yz ( & ) ) o 是包含于u 口yz ( & ) 最大的同余在b = ( 玩) 上定义 二元关系如下 ( n ，6 ) 0 1 3 错( 刍a ， ，s ) 陋= ，) ，6 = ( 6 ，) ， ，6 ) ( uz ( & ) ) o 】 ( 7 ) 口y 1 0 西南大学硕士学位论文半群上的中心同余 则易知如下二元关系船 ( 口，6 ) p b ( a ，5 ) o b , ( v r h ，矗，痴，蠢s 1 ) 【晓舂痴7 = 悫密蠢7 辛m b m 7 = n b n ； 仇6 赢7 ：彘碗7 毒r n c l r a , 7 ：佗o , 7 l ， ( 8 ) 其中( r h 舞s ) 或岳s ) 陋= 1 ，壳= 1 】，( m gs ) 或( n 7gs ) m = 1 ，n 7 = 1 是 b = b a ) 上的一同余 定理4 3 4设s = ( f & ) 是密码群并半群则 z ( s ) = ( a ，6 ) z ( ) ：( 0 ，b ) p s ；( 即n ) ( a ，p ) ( 幻- a ，卢) 一1 c ( g p ) ， 其中记号均来自引理4 3 3 证明记上述等式右边确定的s 上的二元关系为p 若( a ，占) p ，任取r h ，砒矗，r l 最不妨设a ，占& ，仡品，元s ，m 跆，n & ，则 c a l m = h m 毒 = 昔 = 毒 = 同理可证， ( m o , m i ，虎即，碣而。( a ，6 ) p r o ， m 口( 一，6 ) ) = ( 船。矗，亢卟，哦赫( a ，5 ) ，孙。( n 7 q ，6 ) ) ( 据( 6 ) ，其中占= j 臼q 卢= - y o r - y ) ( m b r n ，r h c r 卢，印编l ，6 ) ，苫m b ( m 7 c r y , ，6 ) ) = ( 礼轨，壳q ，6 p 丽( a ，6 ) ，锄( 几7 q ，占) ) ( 据( 7 ) ，( 8 ) 及定理4 2 2 ) ( m b r n 。，晓盯反6 p t 皤r ( b a t , ，6 ) p m ， m 6 ( m 7 盯口，6 ) ) = ( n b n ，u r 7 ，6 p ( 治q ，j ) ，葫6 ( n ，占) ) ( 因为( 也，6 ) ( 帆，5 ) - 1 c ( g 母) ) 晓6 痴：碗赢： h b r n = 壳硫7 = 亭r h e i m = u i n 类似可证r h ：亢= 1 s z ，及不= 蠢= 1 s a 的情况因此，p z ( s ) 若( a ，6 ) z ( s ) ，由引理4 3 2 知，存在a 】，使得( a ， i ) z ( & ) ，不妨设 a = ( n ，g 口) ，6 = ( b ，) ，再由定理4 0 1 易知( n ，6 ) p b 关于任意p 口芦，取 晓= ( 声，阳) ，赢= ( 万，( a 口。，口) 一1 ) ，壳= ( 万，( a 盯。，p ) 一1 ) ，元= ( 万，h 卢) 昂，贝0 7 7 l n ，7 z 2 ( 压反m 即，哦茚( a ，p ) 殇雳缸( 痴即，p ) ) ( 据( 6 ) ) ( 万，h 口( a ，口) ( a 仃a ，口) 一1 ) ( 据( 3 ) 及引理4 3 3 ) ( 厦( a 仃。，p ) 一1 ( a o r a ，口) 危p ) ( 卢卵，壳即，口p 口鼬( a ，卢) 邱声菇( n 7 即，p ) ) u i n ， 西南大学硕士学位论文 半群上的中心同余 进而蒯吼= 壳赫。故 m 6 疵= 壳赫7 = 辛( 新，m 即，声啪声( 6 盯口，口) 踢压葫( 痴即，口) ) = ( 面万，矗即，口p 6 茚( 6 仃口，芦) p 荫前( n 7 盯芦，卢) ) ( 据( 6 ) ) ：= = ( p ，危p ( 溉，卢) ( a c r 口，卢) 一1 ) = ( p ，( a ，p ) 一1 ( 6 a 么，p ) p ) ：= = 争h 口( 6 矿n ，p ) ( a c r a ，卢) 一1 = ( a 盯口，p ) 一1 ( b 仃口，声) 危口 据的任意性，( a 仃q ，p ) ( 6 ，卢) 一1 c ( g p ) 因此，( a ，i i ) p 口 1 2 西南大学硕士学位论文半群上的中心同余 4 4 一些特殊的密码群并半群的中心同余 本节我们将不借助引理4 3 3 所给出的密码群并半群的结构定理，给出正规 密码群并半群，带，及纯正密码群并半群的中心同余的刻画 定理4 4 1设s = ；& ，x 印】是完全单半群的强半格，即一个正规密码 群并半群则 z ( s ) = 【( o ，b ) z ( & ) ：( v p q ) ( a x 。，卢，b x a ，芦) z ( 昂) 证明设等式右端所确定的s 上的二元关系为p 若( n ，6 ) a 仇，m ，n ，1 0 , 只不妨设m 昂，m 7 跆，礼s ，他7 墨则 竹i 口m = n 口他= = 争 ( m ) ( p ，6 ) ( o x 口，6 ) ( m 7 x ，6 ) = ( n x ，y ，6 ) ( o x 口，6 ) ( 礼h ，6 ) ( 其中6 = p q 卢= 7 叩7 ) = = 事( ? 珏x 反6 ) ( 6 x 口，6 ) ( m 。x 芦，6 ) = ( n x - y ，6 ) ( 奴口，6 ) ( 扎) 婶，d ) = = f 7 t ，m 7 = ，l z m 7 类似可证m = 7 1 , = 1 s 1 ，及m = 扎= 1 s 1 的情况因此，p z ( s ) 若( 口，b ) z ( 习，由引理4 3 2 知，存在q y ，使得( o ，6 ) z ( ) 关于任意 p p q ，任取m ，m ，礼，扎码，有 m c z m r = n 口他咎m b m = n l m = = = 专- ( m x 卢，卢) ( o ) ( n ，卢) ( l x 口，卢) = ( n x p ，卢) ( o x a ，卢) ( 几7 x 卢，口) ( 仃l x p ，卢) ( 6 x q ，芦) ( m x p ，卢) = ( n x 反芦) ( 6 x 。，p ) ( 佗x 卢，) ：= = 争m ( a x n ，p ) m 7 = n ( a x d ，p ) 耗7 争m ( b x ，p 弘= n ( b x n ，芦) 讫 争( a x a ，p ，b x a ，卢) z ( 品) 因此，z ( s ) p 口 推论4 4 2 设s = 【y ；g o , ，x 口，口】是群的强半格( c l i f f o r d 半群) 则 z ( s ) = ( n ，b ) 。纩：n 6 1 c ( s ) ， 其中c ( s ) = 口s ：( v s s ) d s = 8 a 证明设p = t ( n ，乡纩：a b 一1 c ( s ) 若( 口，6 ) n 则关于任意m ，m ，n ，死s 有 ， m 口7 7 , = 礼n 礼 = 争 号 昔 ， m a b 一1 概= n a b 一1 轨 ( a b 一1 ) m b m 7 = ( a b 一1 ) n b n 7 ( a b 一1 ) o m b m = ( a b 一1 ) o n b n 7 m b m = n l m 类似可证l n = 7 1 , = 1 s 1 ，及m 7 = 7 l = 1 s 1 的情况因此，p z ( s ) 1 3 西南大学硕士学位论文半群上的中心同余 若( o ，b ) z ( s ) ，由引理4 3 2 知，存在a y ，使得( o ，b ) z ( c a ) ，必然 有( 口，b ) j 纩又由定理4 4 1 知，关于任意pso l ，( a x a ，卢，6 ，卢) z ( g o ) ，即 ( a x 口，p ) ( 6 ，p ) 一1 c ( g p ) 任取s s ，不妨设s g 7 ，有 ( a b 一1 ) s = ( a b 一1 ) x a 。7 ( s x 7 ，a ，y ) = ( s x l ，口7 ) ( 0 6 1 ) x n ，口1 = s ( a b 一1 ) ， 因此，a b 一1 c ( s ) 口 定理4 4 3设b = b e , ) 是一个带( 矩形带的半格) 则 z ( b ) = ( e ，) b r , xb & ：( ，忍b ) 9 e h = g s h 证明记等式右边所确定的b 上的二元关系为j d 若( e ，) p ，关于任意m ，m ，7 1 , ，n b ，显然有 1 n e m = l r l , e 1 1 , t 铸m f m 7 = nfnlne l r l , e 1 1 , m li n = = 当m = l q , = 1 b 1 时， e m = e l l , = 冷f e m 7 = f e n = 净f f m = ，n = = f m 7 = ，n 同理可证，m = 霸7 = 1 的情况因此，p 冬z ( s ) 若( e ，) z ( b ) ，有引理4 3 2 知，( e ，) 玩风关于任意9 ，h b ，有 9 e h = 9 e h 考9 e h = g ( e y e ) h ( 由于e ，b e , ) 哥9 ， = g y ( y e h ) ( 由于( e ，) z ( b ) ) 爿( ! t i ) y ( f h ) = g f ( e h ) j g f e f h = g e ( e h ) ( 由于( e ，) z ( b ) ) = 毒g f h = 9 e h 因此，z ( s ) p 。 口 引理4 4 4设b = 既) 是带，y 是半格关于任意o t y ，设 & = b e , g q 是矩形群关于任意o t ，p a2p ，设p n ，p 是g 。到g 卢的同态且满 足以下条件：关于任意o l ，p ，y o t p2 ( 1 ) 以，口= l a 。；( 2 ) 如，厣鲐。1 = 钆 关于任意z = ( n ，g ) ，s ，= 溉h ) 昂，在s = u a y & 上定义与运算如下； z 幸可= ( a b ，( 9 0 a ，a 卢) ( 加卢，a 卢) ) ( 9 ) 则s 是纯正密码群并半群相反，每个纯正密码群并半群可由此方式构造 证明由引理4 3 3 及纯正密码群并半群的性质易知 口 定理4 4 5 设s 是纯正密码群并半群则 z ( s ) = ( a ，6 ) z ( ) ：( n ，b ) z ( b ) ；( v p q ) ( 9 0 q ，卢) ( 钻。卢) 一1 c ( g p ) ) ， 】4 西南大学硕士学位论文 半群上的中心同余 其中a = ( 口，9 ) ，6 = ( b ，危) ，其余记号均来自引理4 4 4 证明 记等式右端所确定的s 上二元关系p 若( a ，6 ) o f _ p ，则关于任意俄= 沏，m 口) ，克= ( 佗，) s ，m = ( m 7 ，m ) ，死= ( n ，t ，) & ，有 r i m m = 跳珏仁争 m a r e ，( 嫩声6 ) ( 夕气，6 ) ( m ，6 ) ) = ( 珏嬲，( 狮如，5 ) ( 夕如，6 ) ( 死：，q ，占) ) ( 据( 9 ) ，其中6 = p q = 7 q 7 ) 甘( m b m ，( m 卢鲐，6 ) ( 加a ，6 ) ( m ，6 ) ) = ( 礼硫7 ，m 7 钆，6 ) ( 慨，6 ) ( n = r ，q ，6 ) ) ( 由于( a ，6 ) z ( b ) ；( g o a ，6 ) ( h o ，占) 1 c ( g 6 ) ) 牟：夸瓤；矗：靓矗? 。 类似可证晓= 矗= 1 s z ，及赢= 五7 = 1 s 1 的情况因此，p z ( s ) 若 ，占) z ( s ) ，由引理4 3 2 知，存在理y ，使得( a ，占) z ( 岛) 任 取m 昂，礼b ，m ，n 7 b ，若r n o t b = 纰礼，取晓= ，叼) ，壳= m ，h ) ，疵= ( m 7 ，6 ) ，五= ( 礼，) ，贝0 ，晓赢= h h n ，由( a ，6 ) z ( s ) 知m b m = 壳赢因此，m b m = n b n ，( 口，6 ) z ( b ) 关于任意p a ，取仇：m ，七) ，m = ( m ，( 9 靠。卢) 一1 ) ，庇= ( n ，( 9 如，p ) 1 ) ，磊7 = ( 咒7 ，动勘据( 9 ) 知，行记疵= b a n ，而由 ( 磊，舂) z ( s ) 知， 晓赫7 = 庇如考( m y r a 7 ，k ( h o a ，卢) ( g 如，p ) 一1 ) = ( n t m 7 ，( g 以，卢) 一l ( h o 。，卢) 七) = = 号k ( h o a ，卢) ( 夕以，卢) 一1 = ( 夕气，芦) 一1 ( h o a ，声) 七 由是劬的任意性，气，p ) ( 艮，缪) 一1 c c c 芦) 因此，z ( s ) 曼p 口 1 5 西南大学硕士学位论文 参考文献 参考文献 【1 】s b u r r i sa n dh p s a n k a p p a n a v a r ，ac o u r s ei nu n i v e r s a la l g e b r a 【m i n e wy o r k ： s p r i n g e r ，1 9 8 1 【2 】j m h o w i e ，a ni n t r o d u c t i o nt os e m i g r o u pt h e o r y 【m j l o n d o n ：a c a d e m i cp r e s s ，1 9 7 6 3 】3m p e t r i c h 。，n r e i l l y ，c o m p l e t e l yr e g u l a rs e m i g r o u p ，j o h nw i l e y s o n s i n c ，1 9 9 9 【4 】s o n g ，g ，t ，l i u ，g ，x a n dz h a n g ，j g ，ac o n s t r u c t i o no f