姜 楠，張富彬，寧春芳

(大連民族大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，遼寧大連116605)

群論是研究群的結(jié)構(gòu)及其應(yīng)用的數(shù)學(xué)理論，是代數(shù)系統(tǒng)的重要分支，它不僅在物理學(xué)、化學(xué)、力學(xué)、生物學(xué)中有著廣泛的應(yīng)用，其應(yīng)用范圍也深入到科學(xué)技術(shù)的各個(gè)領(lǐng)域［1－2］。尤其是在計(jì)算機(jī)科學(xué)領(lǐng)域的研究和應(yīng)用中，群論已成為非常重要的工具。而且群論也是密碼學(xué)的重要理論基礎(chǔ)，例如組合群論中有些基本問(wèn)題相對(duì)于某個(gè)特定的群是困難問(wèn)題，可以作為構(gòu)造公鑰密碼體制的基礎(chǔ)［3］，還有一些對(duì)稱(chēng)加密算法和非對(duì)稱(chēng)加密算法都是以群論為理論基礎(chǔ)的。群的理論比較抽象難以理解，本文設(shè)計(jì)了一個(gè)判斷群的仿真系統(tǒng)。首先設(shè)計(jì)了對(duì)代數(shù)系統(tǒng)進(jìn)行判斷的算法，進(jìn)而設(shè)計(jì)出判斷給定的代數(shù)系統(tǒng)是否為群的算法，最后通過(guò)Java 程序設(shè)計(jì)實(shí)現(xiàn)了群的判斷系統(tǒng)。

1 系統(tǒng)原理

代數(shù)，也稱(chēng)代數(shù)結(jié)構(gòu)或代數(shù)系統(tǒng)，是指定義有若干運(yùn)算的集合。

定義1:非空集合S 和S 上k 個(gè)一元或二元運(yùn)算f1，f2，…，fk組成的系統(tǒng)稱(chēng)為一個(gè)代數(shù)系統(tǒng)，簡(jiǎn)稱(chēng)代數(shù)。記作＜S，f1，f2，…，fk＞［4］。

定義2:群 ＜G，* ＞是一個(gè)代數(shù)系統(tǒng)，其中二元運(yùn)算* 滿(mǎn)足以下3 條:

(1)結(jié)合律，即對(duì)所有的a，b，c∈G，有

a * (b * c)=(a * b)* c (滿(mǎn)足結(jié)合律的代數(shù)系統(tǒng)為半群);

(2)含幺元，即存在一個(gè)元素e，對(duì)任意元素a∈G，有(含幺半群稱(chēng)為獨(dú)異點(diǎn));

(3)存在逆元，即對(duì)每一個(gè)a ∈G，存在一個(gè)元素a–1∈G，使

a－1* a=a * a－1=e(稱(chēng)G 為群);

簡(jiǎn)單地說(shuō)，群是一個(gè)具有可結(jié)合運(yùn)算，存在幺元，每個(gè)元素存在逆元的代數(shù)系統(tǒng)［4］。

2 算法設(shè)計(jì)

2.1 代數(shù)系統(tǒng)的判斷

代數(shù)系統(tǒng)的判斷就是通過(guò)用戶(hù)自定義的集合和運(yùn)算表，判斷給定的運(yùn)算在相應(yīng)的集合上是否封閉，如果封閉，則上述集合與運(yùn)算構(gòu)成代數(shù)系統(tǒng)，否則不能構(gòu)成代數(shù)系統(tǒng)。判斷運(yùn)算封閉的函數(shù)為judgeAlgebraicSystem()，對(duì)于給定的運(yùn)算表，如果運(yùn)算是封閉的，返回true，否則返回false。將給定的運(yùn)算表中的元素和集合中的元素依次做對(duì)比驗(yàn)證，如果運(yùn)算表中的元素均屬于此集合，則此運(yùn)算是封閉的。算法2.1 具體描述如下:

(1)給定n 個(gè)元素的List 類(lèi)型的集合set，給定n 行n 列的List 類(lèi)型的二維運(yùn)算表operationTable，計(jì)數(shù)器count=0，運(yùn)算表循環(huán)變量i=0，j=0，集合循環(huán)變量k=0;

(2)驗(yàn)證運(yùn)算表中所有的元素是否屬于該集合，依次取出運(yùn)算表中第i 行第j 列元素，與集合set 中元素對(duì)比，通過(guò)語(yǔ)句operationTable. get(i).get(j). equals(set. get(k))進(jìn)行判斷。如果存在相等，則計(jì)數(shù)器count + +，并且跳出k 層循環(huán)，j=j+1，i=i +1;否則k 層循環(huán)結(jié)束后j=j +1，i=i+1;

(3)直到循環(huán)結(jié)束將運(yùn)算表中所有元素驗(yàn)證完畢，執(zhí)行(4)，否則執(zhí)行(2)

(4)若count 的值與運(yùn)算表中元素?cái)?shù)量相等，則構(gòu)成代數(shù)系統(tǒng)，返回true，否則不能構(gòu)成代數(shù)系統(tǒng)，返回false。

2.2 判斷給定的代數(shù)系統(tǒng)是否為半群

在已知給定的系統(tǒng)是代數(shù)系統(tǒng)的基礎(chǔ)上，判斷此代數(shù)系統(tǒng)是否為半群的函數(shù)為judgeCombination()，根據(jù)結(jié)合律公式(a * b)* c=a* (b * c)設(shè)計(jì)算法，首先求出等式左側(cè)前兩個(gè)元素作用的值，然后取其值的下標(biāo)，再與第三個(gè)元素進(jìn)行運(yùn)算，得出結(jié)果;然后求出等式右側(cè)后兩個(gè)元素作用的值，并取其值的下標(biāo)，使第一個(gè)元素與之運(yùn)算，得出結(jié)果，將兩次的結(jié)果進(jìn)行比較如果相等返回true，如果不相等返回false。算法2.2 具體描述如下:

(1)給定n 個(gè)元素的List 類(lèi)型的集合set，給定n 行n 列的List 類(lèi)型的二維運(yùn)算表operationTable，分別初始化代表三個(gè)元素的循環(huán)變量i=0，j=0，k=0;

(2)計(jì)算前兩個(gè)元素運(yùn)算的結(jié)果operationTable.get(i). get(j)，暫存temp1 變量中，計(jì)算出temp1 的值在集合中的地址下標(biāo)set. indexOf(temp1)，暫存add1 變量中;

(3)進(jìn)入k 層循環(huán)，計(jì)算后兩個(gè)元素作用的結(jié)果operationTable.get(j). get(k)，暫存temp2 變量中，計(jì)算出temp2 的值在集合中的地址下標(biāo)set.indexOf(temp2)，暫存add2 變量中，執(zhí)行(4);

(4)驗(yàn)證前兩個(gè)元素運(yùn)算的結(jié)果temp1 與第三個(gè)值運(yùn)算的值，同第一個(gè)元素與后兩個(gè)值運(yùn)算的值temp2 運(yùn)算的值是否相等，通過(guò)語(yǔ)句operationTable.get(add1). get(k). equals(operationTable.get(i).get(add2))進(jìn)行判斷，如果兩次運(yùn)算的值不相等，則代數(shù)系統(tǒng)不滿(mǎn)足結(jié)合律，返回false，結(jié)束程序;如果兩次運(yùn)算的值相等，則k=k+1，j=j+1，i=i+1;

(5)直到所有循環(huán)運(yùn)行結(jié)束，執(zhí)行(6)，否則回到(2);

(6)代數(shù)系統(tǒng)滿(mǎn)足結(jié)合律，代數(shù)系統(tǒng)是半群，返回true。

2.3 判斷半群是否為含幺半群

在給定的代數(shù)系統(tǒng)是半群的基礎(chǔ)上，判斷其是否為含幺半群，這個(gè)判斷函數(shù)為judgeIE()，在半群中存在單位元?jiǎng)t為含幺半群也稱(chēng)為獨(dú)異點(diǎn)。對(duì)集合中任意元素a，如果有a* e=a，e* a=a，則此半群中存在單位元e。

算法2.3 具體描述如下:

(1)給定n 個(gè)元素List 類(lèi)型的集合set，給定n 行n 列的List 類(lèi)型的二維運(yùn)算表operationTable，循環(huán)變量i=0;

(2)進(jìn)入循環(huán)，計(jì)數(shù)器count=0，循環(huán)變量j=0;

(3)如果集合中第i 個(gè)的元素與第j 個(gè)元素運(yùn)算的值等于第j 個(gè)元素，并且第j 個(gè)元素與第i個(gè)元素運(yùn)算的值也等于第j 個(gè)元素，用語(yǔ)句operationTable. get(i). get(j). equals(set. get(j))＆＆operationTable. get(j). get(i). equals(set. get(j))進(jìn)行判斷，如果成立count + +，j=j+1;

(4)如果j 層循環(huán)完畢，判斷count 的值是否等于集合的長(zhǎng)度，如果相等，表明此時(shí)存在單位元，此半群是含幺半群，并且將單位元set. get(i)返回，程序結(jié)束;否則i=i+1;

(5)直到循環(huán)結(jié)束，執(zhí)行(6)，否則回到(2);

(6)代數(shù)系統(tǒng)中不存在單位元，返回false。

2.4 判斷含幺半群是否為群

在給定的代數(shù)系統(tǒng)是含幺半群的基礎(chǔ)上，判斷其是否為群的函數(shù)是judgeInverseElement()，若在含幺半群中每一個(gè)元素都存在逆元，此含幺半群為群，對(duì)代數(shù)系統(tǒng)任意的a 存在a * a－1=e，a－1* a=e，a－1屬于集合set，則此元素存在逆元。算法2.4 具體描述如下:

(1)給定n 個(gè)元素List 類(lèi)型的集合set，給定n 行n 列的List 類(lèi)型的二維運(yùn)算表operationTable與單位元ie，設(shè)置計(jì)數(shù)器count=0，循環(huán)變量i=0，j=0;

(2)利用運(yùn)算表，依次取出運(yùn)算表中第i 行j列元素，驗(yàn)證集合中第i 個(gè)元素與第j 個(gè)元素運(yùn)算的值，同第j 個(gè)元素與第i 個(gè)元素運(yùn)算的值是否同時(shí)為單位元，通過(guò)語(yǔ)句operationTable. get(i).get(j). equals(ie)＆＆operationTable. get(j). get(i).equals(ie)判斷，如果所得的兩個(gè)值同時(shí)為單位元，則計(jì)數(shù)器count+ +，否則j=j+1，i=i+1;

(3)直到循環(huán)結(jié)束，執(zhí)行(4)，否則回到(2);

(4)如果count 的值與集合長(zhǎng)度相等，表明所有的元素均具有逆元，含幺半群是群，返回true，否則表明某個(gè)元素不存在逆元，含幺半群不是群，返回false。

3 系統(tǒng)實(shí)現(xiàn)流程

本系統(tǒng)是通過(guò)Java 語(yǔ)言編程實(shí)現(xiàn)的。對(duì)于一個(gè)非空集合G 以及定義在G 上的代數(shù)運(yùn)算所構(gòu)成的系統(tǒng)，判斷＜G，* ＞其是否為代數(shù)系統(tǒng)，首先需要給定集合set，以及定義在集合上的運(yùn)算構(gòu)成的運(yùn)算表operationTable，通過(guò)類(lèi)JudgeAlgebreic-System 聲明對(duì)象jas，調(diào)用函數(shù)judgeAlgebreicSystem(operationTable，set)，通過(guò)算法2.1 判斷運(yùn)算是否封閉，如果返回true，則運(yùn)算封閉，輸出“運(yùn)算封閉，是代數(shù)系統(tǒng)”，程序繼續(xù)執(zhí)行，如果返回false，運(yùn)算不封閉，＜G，* ＞不是代數(shù)系統(tǒng)，輸出“不是代數(shù)系統(tǒng)”，程序結(jié)束。

在滿(mǎn)足代數(shù)系統(tǒng)的基礎(chǔ)上，通過(guò)類(lèi)JudgeCombination 聲明對(duì)象jc，調(diào)用judgeCombination(operationTable，set)，通過(guò)算法2.2 判斷代數(shù)系統(tǒng)是否滿(mǎn)足結(jié)合律，如果程序返回true，則表明代數(shù)系統(tǒng)滿(mǎn)足結(jié)合律，此時(shí)代數(shù)系統(tǒng)是半群，輸出“運(yùn)算可結(jié)合，此代數(shù)系統(tǒng)是半群”，否則返回false，代數(shù)系統(tǒng)不滿(mǎn)足結(jié)合律，輸出“運(yùn)算不可結(jié)合，此代數(shù)系統(tǒng)不是半群”，程序結(jié)束。

在滿(mǎn)足半群的基礎(chǔ)上，通過(guò)類(lèi)JudgeIE 聲明對(duì)象jie，調(diào)用judgeIE(operationTable，set)，通過(guò)算法2.3 判斷半群是否含有單位元，如果存在，函數(shù)將單位元返回用result 接收，并輸出“單位元，此代數(shù)系統(tǒng)是含幺半群”，否則返回false，輸出“此代數(shù)系統(tǒng)不存在單位元，不是含幺半群”，程序結(jié)束。

在滿(mǎn)足含幺半群的基礎(chǔ)上，通過(guò)類(lèi)JudgeInverseElement 聲明對(duì)象jie2，調(diào)用judgeInverseElement(operationTable，set，result)，通過(guò)算法2.4 驗(yàn)證是否每個(gè)元素均存在逆元，如果返回true，則表明所用元素均存在逆元，輸出“所用的元素均存在逆元，此代數(shù)系統(tǒng)是群”，否則返回false，輸出“部分元素不存在逆元，代數(shù)系統(tǒng)不是群”，程序結(jié)束。

系統(tǒng)實(shí)現(xiàn)流程圖如圖1 。

圖1 系統(tǒng)流程圖

4 結(jié) 論

群論是離散數(shù)學(xué)課程的重要組成部分，也是一種非常重要的代數(shù)系統(tǒng)，在很多領(lǐng)域都有應(yīng)用，尤其是在計(jì)算機(jī)和通信以及信息安全領(lǐng)域有更為廣泛的應(yīng)用。本文主要研究給定集合與運(yùn)算是否構(gòu)成代數(shù)系統(tǒng)、是否構(gòu)成半群和獨(dú)異點(diǎn)，對(duì)給定的代數(shù)系統(tǒng)是否構(gòu)成群的判斷系統(tǒng)的原理與算法設(shè)計(jì)，并且編程實(shí)現(xiàn)了群的判斷系統(tǒng)。該系統(tǒng)把抽象難以理解的代數(shù)中的群論問(wèn)題通過(guò)形象直觀的程序軟件表現(xiàn)出來(lái)，不僅可以幫助學(xué)生更好的理解書(shū)本上學(xué)過(guò)的抽象的難以理解的代數(shù)系統(tǒng)理論，還可以提高學(xué)生的數(shù)學(xué)建模能力、算法分析設(shè)計(jì)能力和程序設(shè)計(jì)能力。既提高了學(xué)生各方面的能力，又培養(yǎng)了學(xué)生的學(xué)習(xí)興趣，可以很好的提高教學(xué)質(zhì)量。

［1］李奴義.淺議群論在化學(xué)中的應(yīng)用［J］.青海師范大學(xué)民族師范學(xué)院學(xué)報(bào)，2012，23(1):95 －96.

［2］何劼. 用群論的基礎(chǔ)知識(shí)理解信號(hào)處理中的一些基本概念［J］.中央民族大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007，16(3):259 －261.

［3］湯學(xué)明，洪 帆，崔國(guó)華. 辮子群上的公鑰加密算法［J］.軟件學(xué)報(bào)，2007，18(3):722 －728.

［4］屈婉玲，耿素云，張立昂. 離散數(shù)學(xué)［M］. 北京:清華大學(xué)出版社，2014.