姚俊萍，李新社

(西安高新技術(shù)研究所)

0 引言

由文獻(xiàn)［1-5］可以看到元素的階對于群的重要性.元素的階是群論中最基本的一個概念.從著名的Burnside問題可以看出，元素的階在群的結(jié)構(gòu)中起著重要的作用.群中元素的階是一個基本的數(shù)量.如果把群看作一個整體，其中的元素就是一個局部，局部和整體有著密不可分的聯(lián)系.為此，考察元素階的作用，可使從局部來看整體，并推導(dǎo)和引申各種不同群的性質(zhì)，進(jìn)而促進(jìn)計算機(jī)科學(xué)和算子理論的應(yīng)用與研究.

1 群元素階定義

設(shè)G為群，a∈G且e是G的么元時，使an=e成立的最小正整數(shù)n稱為元素a的階，記為|a|=n.若這樣的n不存在，則稱元素a的階為無限(或為零).

(1)在＜{0，1}，+2＞群中，因為0是么元，而01=0，12=0，所以0 的階為1，1的階為2.

(2)在整數(shù)加群〈Ⅰ，+〉中，因為0是么元，任意整數(shù)a的任何正整數(shù)冪均不為零，所以只有0的階為1，其余整數(shù)的階皆為無限(或零).

2 元素階的性質(zhì)

許多著名教材中都有關(guān)于群元素階的性質(zhì)論述，但都比較簡單，缺乏系統(tǒng)性，這里借鑒文獻(xiàn)和編著就一些特別需要關(guān)注而且應(yīng)用較多的性質(zhì)及其結(jié)論予以分析研究討論.

(1)在有限群中，每個元素的階均有限.這是因為若某個元素b的階為無限，那么對于任何正整數(shù)i和j，必有i≠j當(dāng)且僅當(dāng)bi≠bj，但這與群中只有有限個元素相矛盾.另外，若元素b的階為n，那么n|m?bm=e成立是顯然的.反過來，若bm=e，而m=pn+q，p，q∈Z，0＜q＜n，則有bm=bpnbq=bq=e，但這與b的階為n相矛盾.

(2)設(shè)群G中元素a的階為n，則|ak|=因為(ak=e，所以，不妨設(shè)，如此則有，但an=e且|a|=n，故，因此t=1，從而成立.由此立即可以得出|ak|=1?(k，n)=1，其中k為任意整數(shù).

(3)在群G中，若|a|=m，|b|=n，(m，n)=1，ab=ba則|ab|=mn.由(ab)mn=amnbmn=e知|ab||mn，不妨設(shè)，如此則有或t|n.當(dāng)t|m時，進(jìn)而，所以t|n;類似地當(dāng)t|n時有t|m，但(m，n)=1，因此t=1，故|ab|=mn成立.

值得指出的是若(m，n)≠1，則|ab|=未必成立.

(4)設(shè)n是交換群G中所有元素的最大階，則G中每個元素x的階都是n的因數(shù)［6］，于是xn=e.

假設(shè)交換群G中元素a的階為n，且達(dá)到最大.對于任意元素x，不妨設(shè)|x|=m.對于m和n，可變換成m=pq，n=st，且(q，t)=1，［m，n］=qt，則|as|=t，|xp|=q，|asxp|=qt=［m，n］，而［m，n］為階，不大于n，因此m|n，故命題成立.

(5)設(shè)G是群，a，b∈G，則ab與ba同階.

(6)設(shè)G是群，a，b∈G，|a|=m，|b|=n，如果ab=ba且(a)∩(b)={e}，則|ab|=［m，n］.

(7)在群G中，設(shè)|a|=n，r是任一整數(shù)，若(n，r)=d，則(ar)=(ad).

(8)設(shè)p，q是互異素數(shù)，|G|=pq，G是可交換群，則G是循環(huán)群.

因為群G是pq階可交換群，顯然G中至少有一個周期為p或q的元，不妨設(shè)a是G中周期為p的元，令H=(a)，則H是G的p階不變子群，商群G/H是q階群.設(shè)G/H的生成元為bH，那么(bH)q=bqH=H，于是bq∈H.b的周期不能為p.因為由bp=e∈H，bq∈H，(p，q)=1，可得b∈H，矛盾，故b的階只能為q或pq，若為pq，則G=(b)是循環(huán)群.若為q，則G=(ab)是循環(huán)群.

(9)設(shè)G是一個群，a與b的階分別為m，n，ab=ba，則元素ab的階是［m，n］的約數(shù)且G中存在階是［m，n］的元素.

(10)若群G的元素a的階有限，元素b的階無限，ab=ba，則ab是無限階元素.

3 元素階與典型群的關(guān)系

(1)在群G中，若a∈G，e是G的么元，|a|=n，則{a，a2，a3，…，an}是G的子群.{a，a2，a3，…，an}關(guān)于G中運(yùn)算構(gòu)成子獨(dú)異點(diǎn)是顯然的.此外，對于任意的元素x=ai∈{a，a2，a3，…，an}，|ai|=，于是x-1=因此{(lán)a，a2，a3，…，an}是G的子群.這里需要注意的是，若|G|=m，則由拉格朗日定理有n|m.

(2)一個素數(shù)階群G肯定是循環(huán)群.因為在該群中，肯定存在非單位元素a，其階是有限的，于是|a|/|G|，然而|G|是素數(shù)，所以|a|=|G|，因此素數(shù)階群G可以表示為{a，a2，a3，…，，故G定是循環(huán)群.

(3)根據(jù)循環(huán)群的定義，任意循環(huán)群G的階由其生成元決定，而且循環(huán)群G的子群S肯定是循環(huán)群.假設(shè)G={a，a2，a3，…}，再設(shè)ik=min{is|is＞0}，若S中任意元素的冪是ik倍數(shù)，那么S是循環(huán)群.否則假設(shè)S中存在元素x的冪ip不是ik倍數(shù)，那么ip=qik+r，0＜r＜ik，于是，但G，而這與ik=min{is|is＞0}相矛盾，故S是循環(huán)群.

(4)設(shè)G是交換群，那么G的所有有限階元素的集合H關(guān)于G的運(yùn)算是G的不變子群(正規(guī)子群).假設(shè)a∈H，b∈H，因為G可交換，a和b的階均有限，所以|ab|≤［|a|，|b|］，也有限，即ab∈H;又因為a-1與a同階，也就是說a-1∈H;所以H是G的子群，再根據(jù)交換群的子群都是正規(guī)子群，可得H關(guān)于G的運(yùn)算是G的不變子群(正規(guī)子群).

4 元素階與數(shù)模之間的關(guān)系

模m剩余類關(guān)于乘法運(yùn)算×m構(gòu)成的代數(shù)通常不是群，但一個元素a若與模m互素，則該元素存在逆元，其階定義為使an≡1 modm成立的最小正整數(shù)n，記為δm(a).δm(a)不但具有與群元素階類似的性質(zhì)，而且根據(jù)歐拉定理還具有下面兩條重要性質(zhì).

(1)若m＞1，(a，m)=1，則aφ(m)≡1 modm，于是δm(a)/φ(m).特別地，若m=p為素數(shù)，δm(a)/(p-1).注意這里的φ(m)就是m的歐拉函數(shù)值.

(2)若(m，n)=1，(a，mn)=1，則δmn(a)=［δm(a)，δn(a)］.這個結(jié)論易由(1)得出.

事實上，數(shù)論里關(guān)于元素階的討論與群中方法完全一致，只不過應(yīng)用在整個整數(shù)范圍上.

5 元素階概念在實際生活和信息安全中的運(yùn)用

(1)將編號為1～52的卡片分為1～26，27～52兩組，交錯互相插入.則這樣的交錯插入重復(fù)8次后就會恢復(fù)到原來的牌序.

洗牌前1 2 3 4 5 6 7 8 9…26 27 28…49 50 51 52

洗牌后1 27 2 28 3 29 4 30 5…39 14 40…25 51 26 52

第一次插入相當(dāng)對1～52作一次置換p=(1)(2，27，14，33，17，9，5，3)(4，28，40，46，49，25，13，7)(6，29，15，8，30，41，21，11)(10，31，16，34，43，22，37，19)(12，32，42，47，24，38，45，23)(18，35)(20，36，44，48，50，51，26，39)(52)，其中最長的輪換為8階.

因為所有小于8階的輪換階數(shù)都是8的因子，k階輪換重復(fù)k的倍次后恢復(fù)原狀，故結(jié)論成立.美國的研究人員認(rèn)為，撲克牌洗7次最合適.

事實上，知道洗牌方法，就可寫出對應(yīng)的置換，于是將該置換表示成不相交輪換的乘積，求出各輪換階的最小公倍數(shù)m，得出撲克牌在該洗牌方法下重復(fù)m次后恢復(fù)到初始狀態(tài).

(2)根據(jù)置換階計算規(guī)律可以分析研究某種只進(jìn)行置換的特殊密碼黑盒

向黑盒輸入一列數(shù)a1，a2，a3，…，an，觀察黑盒輸出結(jié)果，比如為ai1，ai2，…，ain，再將結(jié)果重新輸入，再觀察結(jié)果，肯定某次就恢復(fù)到最初狀態(tài)，記錄下這個次數(shù).如果這樣次數(shù)較少，實際上該黑盒就被可以破譯了.因為根據(jù)黑盒輸出結(jié)果反復(fù)迭代記錄下的次數(shù)就得到向黑盒輸入的初始值.

(3)在信息安全基礎(chǔ)理論研究和運(yùn)用中，大量涉及到群元素階的性質(zhì).比如經(jīng)常安全素數(shù)的使用.安全素數(shù)是一個足夠大的形如2q+1的素數(shù)p，其中q也是素數(shù)，而且乘法群Z*P有四個子群:①只有數(shù)1組成的平凡子群;②僅由1和p-1組成的大小為2的子群;③一個大小為q的子群;④一個大小為2q的整個群.兩個子群容易避免，第三個即為想要的子群.考慮所有能夠?qū)懗闪硪粩?shù)平方(當(dāng)然要模p)的模p數(shù)集合.事實上，對于1，…，p-1中恰好有一半的數(shù)是平方數(shù)，一半是非平方數(shù)，但整個群的生成元是非平方數(shù)(如果是平方數(shù)，則它的任何次冪都不能產(chǎn)生非平方數(shù)，于是不能生成整個群).如何使用安全素數(shù)?選擇(p，q)使得p=2q+1，并且p和q都是素數(shù)，在2，…，p-2中隨機(jī)選擇一個a，令g=a2(modp)，檢驗g≠1，且g≠p-1(否則重選)，這樣產(chǎn)生的參數(shù)(p，q，g)適合Diffle-Helleman協(xié)議.當(dāng)Alice或Bob收到的應(yīng)該是g的方冪的值時，必須檢查收到的這個值的確位于g生成的子群中.當(dāng)且僅當(dāng)rq≡1(modp)時，數(shù)r是平方數(shù).此時也要禁止使用數(shù)1，完整的檢驗是r≠1且rq≡1(modp).事實上這里的關(guān)鍵問題是r關(guān)于模p階，要求p足夠大.

6 結(jié)束語

研究群元素階的性質(zhì)不但對于分析群的結(jié)構(gòu)有重要作用，而且對建立在群上，特別是某個循環(huán)群上的密碼系統(tǒng)安全性分析至關(guān)重要.為了建立一個安全的密鑰空間，常常需要群的階很高，于是找到高階元素顯得尤為重要.這些研究對計算機(jī)科學(xué)和對算子理論的應(yīng)用有重要貢獻(xiàn).此外，群元素階的研究對分析環(huán)結(jié)構(gòu)也有很大作用.

［1］ 孫宗明.群的元素的階的某些問題［J］.泰山師范學(xué)院學(xué)報，2003，25(3):1-7.

［2］ 魏貴民.有限群可解與群的階［J］.成都理工大學(xué)學(xué)報，2009，36(1):92-93.

［3］ 黃學(xué)軍.關(guān)于群中元素階的幾個結(jié)論［J］.成都教育學(xué)院學(xué)報，2006，20(6):49-64.

［4］ 楊冰.關(guān)于群中乘積元素的階［J］.大學(xué)數(shù)學(xué)，2005，21(5):25-128.