群的判斷算法設(shè)計

姜 楠，張富彬，寧春芳

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

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

1 系統(tǒng)原理

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

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

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

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

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

(2)含幺元，即存在一個元素e，對任意元素a∈G，有(含幺半群稱為獨異點);

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

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

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

2 算法設(shè)計

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

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

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

(2)驗證運算表中所有的元素是否屬于該集合，依次取出運算表中第i 行第j 列元素，與集合set 中元素對比，通過語句operationTable. get(i).get(j). equals(set. get(k))進行判斷。如果存在相等，則計數(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é)束將運算表中所有元素驗證完畢，執(zhí)行(4)，否則執(zhí)行(2)

(4)若count 的值與運算表中元素數(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è)計算法，首先求出等式左側(cè)前兩個元素作用的值，然后取其值的下標(biāo)，再與第三個元素進行運算，得出結(jié)果;然后求出等式右側(cè)后兩個元素作用的值，并取其值的下標(biāo)，使第一個元素與之運算，得出結(jié)果，將兩次的結(jié)果進行比較如果相等返回true，如果不相等返回false。算法2.2 具體描述如下:

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

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

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

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

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

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

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

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

算法2.3 具體描述如下:

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

(2)進入循環(huán)，計數(shù)器count=0，循環(huán)變量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 層循環(huán)完畢，判斷count 的值是否等于集合的長度，如果相等，表明此時存在單位元，此半群是含幺半群，并且將單位元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()，若在含幺半群中每一個元素都存在逆元，此含幺半群為群，對代數(shù)系統(tǒng)任意的a 存在a * a－1=e，a－1* a=e，a－1屬于集合set，則此元素存在逆元。算法2.4 具體描述如下:

(1)給定n 個元素List 類型的集合set，給定n 行n 列的List 類型的二維運算表operationTable與單位元ie，設(shè)置計數(shù)器count=0，循環(huán)變量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)判斷，如果所得的兩個值同時為單位元，則計數(shù)器count+ +，否則j=j+1，i=i+1;

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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

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

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

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