群的判断算法设计

姜 楠，张富彬，宁春芳

(大连民族大学 计算机科学与工程学院，辽宁大连116605)

群论是研究群的结构及其应用的数学理论，是代数系统的重要分支，它不仅在物理学、化学、力学、生物学中有着广泛的应用，其应用范围也深入到科学技术的各个领域［1－2］。尤其是在计算机科学领域的研究和应用中，群论已成为非常重要的工具。而且群论也是密码学的重要理论基础，例如组合群论中有些基本问题相对于某个特定的群是困难问题，可以作为构造公钥密码体制的基础［3］，还有一些对称加密算法和非对称加密算法都是以群论为理论基础的。群的理论比较抽象难以理解，本文设计了一个判断群的仿真系统。首先设计了对代数系统进行判断的算法，进而设计出判断给定的代数系统是否为群的算法，最后通过Java 程序设计实现了群的判断系统。

1 系统原理

代数，也称代数结构或代数系统，是指定义有若干运算的集合。

定义1:非空集合S 和S 上k 个一元或二元运算f1，f2，…，fk组成的系统称为一个代数系统，简称代数。记作＜S，f1，f2，…，fk＞［4］。

定义2:群 ＜G，* ＞是一个代数系统，其中二元运算* 满足以下3 条:

(1)结合律，即对所有的a，b，c∈G，有

a * (b * c)=(a * b)* c (满足结合律的代数系统为半群);

(2)含幺元，即存在一个元素e，对任意元素a∈G，有(含幺半群称为独异点);

(3)存在逆元，即对每一个a ∈G，存在一个元素a–1∈G，使

a－1* a=a * a－1=e(称G 为群);

简单地说，群是一个具有可结合运算，存在幺元，每个元素存在逆元的代数系统［4］。

2 算法设计

2.1 代数系统的判断

代数系统的判断就是通过用户自定义的集合和运算表，判断给定的运算在相应的集合上是否封闭，如果封闭，则上述集合与运算构成代数系统，否则不能构成代数系统。判断运算封闭的函数为judgeAlgebraicSystem()，对于给定的运算表，如果运算是封闭的，返回true，否则返回false。将给定的运算表中的元素和集合中的元素依次做对比验证，如果运算表中的元素均属于此集合，则此运算是封闭的。算法2.1 具体描述如下:

(1)给定n 个元素的List 类型的集合set，给定n 行n 列的List 类型的二维运算表operationTable，计数器count=0，运算表循环变量i=0，j=0，集合循环变量k=0;

(2)验证运算表中所有的元素是否属于该集合，依次取出运算表中第i 行第j 列元素，与集合set 中元素对比，通过语句operationTable. get(i).get(j). equals(set. get(k))进行判断。如果存在相等，则计数器count + +，并且跳出k 层循环，j=j+1，i=i +1;否则k 层循环结束后j=j +1，i=i+1;

(3)直到循环结束将运算表中所有元素验证完毕，执行(4)，否则执行(2)

(4)若count 的值与运算表中元素数量相等，则构成代数系统，返回true，否则不能构成代数系统，返回false。

2.2 判断给定的代数系统是否为半群

在已知给定的系统是代数系统的基础上，判断此代数系统是否为半群的函数为judgeCombination()，根据结合律公式(a * b)* c=a* (b * c)设计算法，首先求出等式左侧前两个元素作用的值，然后取其值的下标，再与第三个元素进行运算，得出结果;然后求出等式右侧后两个元素作用的值，并取其值的下标，使第一个元素与之运算，得出结果，将两次的结果进行比较如果相等返回true，如果不相等返回false。算法2.2 具体描述如下:

(1)给定n 个元素的List 类型的集合set，给定n 行n 列的List 类型的二维运算表operationTable，分别初始化代表三个元素的循环变量i=0，j=0，k=0;

(2)计算前两个元素运算的结果operationTable.get(i). get(j)，暂存temp1 变量中，计算出temp1 的值在集合中的地址下标set. indexOf(temp1)，暂存add1 变量中;

(3)进入k 层循环，计算后两个元素作用的结果operationTable.get(j). get(k)，暂存temp2 变量中，计算出temp2 的值在集合中的地址下标set.indexOf(temp2)，暂存add2 变量中，执行(4);

(4)验证前两个元素运算的结果temp1 与第三个值运算的值，同第一个元素与后两个值运算的值temp2 运算的值是否相等，通过语句operationTable.get(add1). get(k). equals(operationTable.get(i).get(add2))进行判断，如果两次运算的值不相等，则代数系统不满足结合律，返回false，结束程序;如果两次运算的值相等，则k=k+1，j=j+1，i=i+1;

(5)直到所有循环运行结束，执行(6)，否则回到(2);

(6)代数系统满足结合律，代数系统是半群，返回true。

2.3 判断半群是否为含幺半群

在给定的代数系统是半群的基础上，判断其是否为含幺半群，这个判断函数为judgeIE()，在半群中存在单位元则为含幺半群也称为独异点。对集合中任意元素a，如果有a* e=a，e* a=a，则此半群中存在单位元e。

算法2.3 具体描述如下:

(1)给定n 个元素List 类型的集合set，给定n 行n 列的List 类型的二维运算表operationTable，循环变量i=0;

(2)进入循环，计数器count=0，循环变量j=0;

(3)如果集合中第i 个的元素与第j 个元素运算的值等于第j 个元素，并且第j 个元素与第i个元素运算的值也等于第j 个元素，用语句operationTable. get(i). get(j). equals(set. get(j))＆＆operationTable. get(j). get(i). equals(set. get(j))进行判断，如果成立count + +，j=j+1;

(4)如果j 层循环完毕，判断count 的值是否等于集合的长度，如果相等，表明此时存在单位元，此半群是含幺半群，并且将单位元set. get(i)返回，程序结束;否则i=i+1;

(5)直到循环结束，执行(6)，否则回到(2);

(6)代数系统中不存在单位元，返回false。

2.4 判断含幺半群是否为群

在给定的代数系统是含幺半群的基础上，判断其是否为群的函数是judgeInverseElement()，若在含幺半群中每一个元素都存在逆元，此含幺半群为群，对代数系统任意的a 存在a * a－1=e，a－1* a=e，a－1属于集合set，则此元素存在逆元。算法2.4 具体描述如下:

(1)给定n 个元素List 类型的集合set，给定n 行n 列的List 类型的二维运算表operationTable与单位元ie，设置计数器count=0，循环变量i=0，j=0;

(2)利用运算表，依次取出运算表中第i 行j列元素，验证集合中第i 个元素与第j 个元素运算的值，同第j 个元素与第i 个元素运算的值是否同时为单位元，通过语句operationTable. get(i).get(j). equals(ie)＆＆operationTable. get(j). get(i).equals(ie)判断，如果所得的两个值同时为单位元，则计数器count+ +，否则j=j+1，i=i+1;

(3)直到循环结束，执行(4)，否则回到(2);

(4)如果count 的值与集合长度相等，表明所有的元素均具有逆元，含幺半群是群，返回true，否则表明某个元素不存在逆元，含幺半群不是群，返回false。

3 系统实现流程

本系统是通过Java 语言编程实现的。对于一个非空集合G 以及定义在G 上的代数运算所构成的系统，判断＜G，* ＞其是否为代数系统，首先需要给定集合set，以及定义在集合上的运算构成的运算表operationTable，通过类JudgeAlgebreic-System 声明对象jas，调用函数judgeAlgebreicSystem(operationTable，set)，通过算法2.1 判断运算是否封闭，如果返回true，则运算封闭，输出“运算封闭，是代数系统”，程序继续执行，如果返回false，运算不封闭，＜G，* ＞不是代数系统，输出“不是代数系统”，程序结束。

在满足代数系统的基础上，通过类JudgeCombination 声明对象jc，调用judgeCombination(operationTable，set)，通过算法2.2 判断代数系统是否满足结合律，如果程序返回true，则表明代数系统满足结合律，此时代数系统是半群，输出“运算可结合，此代数系统是半群”，否则返回false，代数系统不满足结合律，输出“运算不可结合，此代数系统不是半群”，程序结束。

在满足半群的基础上，通过类JudgeIE 声明对象jie，调用judgeIE(operationTable，set)，通过算法2.3 判断半群是否含有单位元，如果存在，函数将单位元返回用result 接收，并输出“单位元，此代数系统是含幺半群”，否则返回false，输出“此代数系统不存在单位元，不是含幺半群”，程序结束。

在满足含幺半群的基础上，通过类JudgeInverseElement 声明对象jie2，调用judgeInverseElement(operationTable，set，result)，通过算法2.4 验证是否每个元素均存在逆元，如果返回true，则表明所用元素均存在逆元，输出“所用的元素均存在逆元，此代数系统是群”，否则返回false，输出“部分元素不存在逆元，代数系统不是群”，程序结束。

系统实现流程图如图1 。

图1 系统流程图

4 结 论

群论是离散数学课程的重要组成部分，也是一种非常重要的代数系统，在很多领域都有应用，尤其是在计算机和通信以及信息安全领域有更为广泛的应用。本文主要研究给定集合与运算是否构成代数系统、是否构成半群和独异点，对给定的代数系统是否构成群的判断系统的原理与算法设计，并且编程实现了群的判断系统。该系统把抽象难以理解的代数中的群论问题通过形象直观的程序软件表现出来，不仅可以帮助学生更好的理解书本上学过的抽象的难以理解的代数系统理论，还可以提高学生的数学建模能力、算法分析设计能力和程序设计能力。既提高了学生各方面的能力，又培养了学生的学习兴趣，可以很好的提高教学质量。

［1］李奴义.浅议群论在化学中的应用［J］.青海师范大学民族师范学院学报，2012，23(1):95 －96.

［2］何劼. 用群论的基础知识理解信号处理中的一些基本概念［J］.中央民族大学学报(自然科学版)，2007，16(3):259 －261.

［3］汤学明，洪 帆，崔国华. 辫子群上的公钥加密算法［J］.软件学报，2007，18(3):722 －728.

［4］屈婉玲，耿素云，张立昂. 离散数学［M］. 北京:清华大学出版社，2014.