軌道的數(shù)量性質(zhì)及在密碼學(xué)中的應(yīng)用

1、單位代碼10476學(xué)號1201180004分類號0152.1耳出牝牝* f碩士學(xué)位論文軌道的數(shù)量性質(zhì)及在密碼學(xué)中的應(yīng)用學(xué)科、專業(yè)：基礎(chǔ)數(shù)學(xué)研究方向：申請學(xué)位類別：申 請人：指導(dǎo)教師：有限群論理學(xué)碩士耿旭旭趙先鶴副教授二O五年四月獨創(chuàng)性聲明本人鄭重聲明：所呈交的學(xué)位論文是我個人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研 究成果.盡我所知，除r文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人己經(jīng)發(fā) 表或撰寫的研究成果，也不包含為獲得河南師范大學(xué)或其他教育機構(gòu)的學(xué)位或證書所使用 過的材料.與我一同工作的同志對本研究所做的任何貢獻(xiàn)均己在論文中作了明確的說明并 表示了謝意.簽名：件感起 日期：笠關(guān)于論文使用

2、授權(quán)的說明本人完全了解河南師范大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定即：有權(quán)保留并向國家 有關(guān)部門或機構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán)河南師范大 學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃 描等復(fù)制手段保存、匯編學(xué)位論文。（保密的學(xué)位論文在解密后適用本授權(quán)書）THE ARITHMETICAL PROPERTIES OFORBITS AND APPLICATIONS INCRYPTOGRAPHYA Dissertation Submitted tothe Graduate School of Henan Normal Universityin

3、 Partial Fulfillment of the Requirementsfor the Degree of Master of ScienceByGeng XuxuSupervisor: Prof. Zhao XianheApril, 2015軌道作為一個重要的研究分支，在有限群論以及密碼學(xué)中都占有重要的地位.一方面, 在有限群論中，我們研究了一種特殊的軌道一共猊類，利用共軸類的數(shù)量性質(zhì)研究了具有 兩個最長的非中心G-共貌類長的正規(guī)子群的結(jié)構(gòu)；另一方面，作為軌道數(shù)量性質(zhì)的應(yīng)用，我 們研究了兩類具有特殊線性結(jié)構(gòu)點的平衡旋轉(zhuǎn)對稱布爾函數(shù)的計數(shù)問題，得到了一些新的 結(jié)果.本文主要做了以下兩個

4、方面的工作：在有限群論中，共軸類作為一種特殊的軌道，在有限群結(jié)構(gòu)的研究中占有重要地位. 本文的第三章，主要從正規(guī)子群N的兩個最長的非中心G-共輛類長的數(shù)量性質(zhì)出發(fā)，研究 了正規(guī)子群N的結(jié)構(gòu).作為軌道數(shù)量性質(zhì)的應(yīng)用，在本文的第四章，基于對旋轉(zhuǎn)對稱軌道和自共貌軌道的 計算，結(jié)合線性結(jié)構(gòu)點的性質(zhì)，分別給出了當(dāng)n取不同數(shù)時，同時具有平衡性以及線性結(jié)構(gòu) 點的旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù).關(guān)鍵詞：軌道，正規(guī)子群，線性結(jié)構(gòu)點，旋轉(zhuǎn)對稱布爾函數(shù)，平衡函數(shù)ABSTRACTOrbit is a.n important research branch and pla.ys an important role in fin

5、ite group and cryptology. On the one hand, a specical kind of orbitthe conjugacy classes have been studied in the finite groups. Using the arithmetical condition of the conjugacy classes, we investigate the structure of the normal subgroup with the two longest G-conjugacy classes; On the other hand,

6、 as a application of the arithmetical condition of the orbits, we count the balanced rotation symmetirc Boolean functions which have two special linear structures. Several new results are obtained. The main results of this paper are the following:In the theory of finite groups, the conjugacy classes

7、 as a special orbit pla.y an important role in the research of the structure of finite groups. In chapter 3 of this paper, mainly from the arithmetical condition of the two longest G-conjugacy classes of N, the structure of N has been studied.As a application of the arithmetical condition of the orb

8、its, in chapter 4 of this paper, based on the calculation of rotation symmetric orbits and self-conjugate orbits and combined with the properties of the special linear structures, we count the different variable balanced rotation symmetric Boolean functions which lia.ve two special linear structures

9、.KEY WORDS: orbit, normal subgroup, linear structures, rotation symmetric Boolean functions(RSBF), balanced functions TOC o 1-5 h z 摘要 I HYPERLINK l bookmark20 o Current Document ABSTRACTIII HYPERLINK l bookmark27 o Current Document 第一章緒論 1 HYPERLINK l bookmark30 o Current Document 1.1研究背景 2 HYPERLI

10、NK l bookmark38 o Current Document 1.2本文工作的意義 7 HYPERLINK l bookmark41 o Current Document 1.3有待解決的問題7 HYPERLINK l bookmark44 o Current Document 第二章預(yù)備知識9 HYPERLINK l bookmark47 o Current Document 2.1基本群論知識 9 HYPERLINK l bookmark50 o Current Document 2.2基本密碼學(xué)知識 9 HYPERLINK l bookmark53 o Current Docum

11、ent 第三章關(guān)于最大G-共軸類長的數(shù)量性質(zhì)13 HYPERLINK l bookmark56 o Current Document 3.1關(guān)于共輾類長的一些主要引理133.2主要結(jié)果14 HYPERLINK l bookmark67 o Current Document 第四章兩類具有特殊線性結(jié)構(gòu)點的平衡旋轉(zhuǎn)對稱函數(shù)的計數(shù)21 HYPERLINK l bookmark70 o Current Document 主要引理21主要結(jié)果21 HYPERLINK l bookmark83 o Current Document 參考文獻(xiàn) 41 HYPERLINK l bookmark123 o Cur

12、rent Document 致謝 45攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄47獨創(chuàng)性聲明 49第一章緒論眾所周知，群論與密碼學(xué)關(guān)系甚為密切，群論在密碼學(xué)中的應(yīng)用也十分廣泛，例如交換 代數(shù)在公鑰密碼上的應(yīng)用、置換理論在分組密碼中的應(yīng)用等.值得一提的是，軌道以及軌 道長的問題引起了不同領(lǐng)域?qū)W者們的廣泛關(guān)注.一方面，在有限群論中，一種特殊的軌道 即共貌類在有限群結(jié)構(gòu)的研究中占有重要地位.人們從共輛類的某些數(shù)量性質(zhì)(如：共貌類 的個數(shù)、共粒類的長、共猊類長度的個數(shù)等)入手對有限群的結(jié)構(gòu)展開了研究，涌現(xiàn)出大量 新的成果.另一方面，在密碼學(xué)中，對軌道以及軌道長的分析還能進(jìn)一步研究布爾函數(shù)的 相關(guān)性質(zhì).經(jīng)過密碼學(xué)

13、者的不斷努力，滿足某些特殊性質(zhì)(如：平衡性、彈性、相關(guān)免疫性 等)的布爾函數(shù)的個數(shù)問題等都取得了豐碩的成果.在此，所謂的軌道是如下定義：定義1.1.1設(shè)有限群G作用于集合。上，稱二元素/? e。為等價的，記作。8,如 果存在z e G,使武=/?.易驗證關(guān)系“”是Q上的等價關(guān)系. Q對“”的一個等價類叫 做G在。上的一個軌道.一個軌道所包含的元素個數(shù)叫做該軌道的長.下面的Burnside引理給出群G作用于。上的軌道個數(shù)：定理1.1.1(Burnside引理)設(shè)有限群G作用于集合Q上，若用k表示群G在集合。上作用 所產(chǎn)生的軌道個數(shù)，則k =點 |X(g)|,其中乂0) = ( | a e = a

14、.g&G對于a 令aG = ax | x E G,則。G是G的包含點。的軌道.軌道qG的長度由下面的定理給出：本研究得到國家自然科學(xué)基金(10771172)項目的資助. 定理1.1.2設(shè)有限群G作用于集合。上，aeQ,貝I= |G : Ga,其中G。= rr | a; 6 G, ax = a.特別的，軌道疽7的長度是|G|的因子.需要指出的是，在定義1.1.1中，若令Q = G,此時。所在的軌道即為q所在的共貌類.在 有限群的研究領(lǐng)域中，不少群論工作者從共軸類的某些數(shù)量性質(zhì)（如：共輒類的個數(shù)、共軸 類的長、共貌類長度的個數(shù)等）入手對有限群的結(jié)構(gòu)展開了研究，涌現(xiàn)出大量新的成果（見 文獻(xiàn)2, 3,

15、 4, 5, 6, 7等）.本文的第三章內(nèi)容也就是對共軸類的長度與有限群之間的關(guān)系 進(jìn)行了一定的研究.另一方面，若令Q =理，其中理為凡上的泌隹向量空間，G = Cm*是n階循環(huán)置換 群.此時G作用于。上形成的軌道可用于研究密碼學(xué)中平衡的布爾函數(shù)的個數(shù)問題.根據(jù) 平衡性，得到相應(yīng)的方程組，通過解方程組得到平衡函數(shù)的個數(shù).然而，旋轉(zhuǎn)對稱布爾函數(shù) 由Pieprzyk和Qu在文獻(xiàn)8中首次提出之后，密碼學(xué)者發(fā)現(xiàn)此類函數(shù)具有良好的密碼性質(zhì), 這更激發(fā)了人們對旋轉(zhuǎn)對稱布爾函數(shù)研究的興趣.近年來，不少密碼學(xué)者進(jìn)一步圍繞旋轉(zhuǎn) 對稱布爾函數(shù)的計數(shù)問題給出了新的研究成果.特別的，文獻(xiàn)9給出了以全1向量為線性結(jié) 構(gòu)

16、點的旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù)，考慮到這種情形我們不禁會問：兩類以全1向量為線性 結(jié)構(gòu)點的平衡的旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù)能否確定呢？這就是本文第四章所做的主要內(nèi) 容.1.1研究背景（一）、共輒類的數(shù)量性質(zhì)與有限群的超可解性共軸類的長度以及個數(shù)是有限群中重要的算術(shù)量，通過研究共貌類的一些數(shù)量性質(zhì)來 刻畫有限群的結(jié)構(gòu)是有限群理論研究的重要課題，也是近來有限群理論研究的熱點問題.利 用共輒類研究有限群可以追溯到Landau證明的一個早期結(jié)果:對給定的自然數(shù)r,當(dāng) i r）為自然數(shù)時，方程看 + + . + =】（*）有且僅有有限多個解.令0(1 2 )為有限群G的全體共軸類的代表且= |Cg(免)|,則類

17、方程潟赤+ ，+ + / = 1即為方程(*)的一個解，因此對給定的自然數(shù)，有r個共輒類的有 限群G只有有限多個.因此，共輒類的數(shù)量性質(zhì)(共貌類的個數(shù)及長度)是如何影響有限群 的結(jié)構(gòu)是群論學(xué)家的興趣所在.著名群論學(xué)家Baer首先應(yīng)用文獻(xiàn)2的Burnside定理研究了素數(shù)幕階元具有素數(shù)幕共 貌類長的有限群的結(jié)構(gòu)，開辟了這一研究的先河.自此，人們對共貌類的研究產(chǎn)生了濃厚 的興趣，許多群論工作者紛紛加入到這一研究的行列中來，也得到了一系列有趣的結(jié)果, 如3, 10, 11, 12, 13, 14, 15, 16, 17,等等.從以上研究可以看出，人們可以從不同角度對共 輒類提出各種各樣的問題，其中，

18、在文獻(xiàn)3中，作者研究了兩個最長的非中心共輒類長的 數(shù)量性質(zhì)對有限群結(jié)構(gòu)的影響.定理1.1.3令G是有限群，假設(shè)n n是N的兩個最長的非中心G-共柄類長，滿足(m,n) = 1.如果n整除|N/(Z(G) C N),那么或者N/(Z(G)CN)是一個素數(shù)幕階群或者；0v(a)和CnQ)均交換且0v(a) A CNb) = Z(G) n N.N中所有元素的G-共柄類長是1, m, n.(m) N/Z(N)是一個以CN(a)/Z(N)為核，CN(b)/Z(N)為補的Frobenius群.注意到，在文獻(xiàn)18中Chilag-Herzog對有限群G的共輒類長的數(shù)量性質(zhì)進(jìn)行研究,得到:定理1.1.5若群G的

19、所有共瓶類長無平方因子，則G超可解.基于定理1.1.4以及定理1.1.5,自然考慮：對于正規(guī)子群N的兩個最長的非中心G-共軸 類長，若它們互素且無平方因子時，正規(guī)子群N的結(jié)構(gòu)又會發(fā)生什么樣的變化呢？基于對 這一想法的思考，得到了本文第三章的主要結(jié)果，如下：定理3.2.1設(shè)G是一個有限群，N是G的一個正規(guī)子群.設(shè)a, b e N, bG = m, |aG| = n.假設(shè)m n是N的兩個最長的非中心G-共柄類長，滿足(m,n) = 1且n均無平方因 子，那么N超可解.如果N/Z(N)不是一個素數(shù)羸階群，那么N/Z(N)是一個Frobenius群.(二)、軌道在密碼學(xué)中的研究背景密碼學(xué)是一門古老而年

20、輕的科學(xué)，作為表示邏輯運算的布爾函數(shù)是研究密碼學(xué)和密碼 技術(shù)的重要工具，密碼算法的許多安全性問題都可以歸結(jié)為該密碼算法所使用的邏輯函數(shù) 的性質(zhì)上.因此，在密碼學(xué)領(lǐng)域中，學(xué)者們對布爾函數(shù)進(jìn)行了大量研究.特別的，對于滿足 一定性質(zhì)的布爾函數(shù)的構(gòu)造與計數(shù)成為近年來密碼學(xué)者們的研究熱點.最初由Pieprzyk和Qu提出的旋轉(zhuǎn)對稱布爾函數(shù)，由于它很好地迎合了MD4, NID5以 及HAVAL這些Hash密碼算法需要高效執(zhí)行的客觀要求，因此，它被應(yīng)用于這些Hash算法 的實現(xiàn)中8.隨著文獻(xiàn)19, 20, 21, 22等對旋轉(zhuǎn)對稱布爾函數(shù)的進(jìn)一步分析與研究后，人們 發(fā)現(xiàn)這一類具有特殊代數(shù)結(jié)構(gòu)的布爾函數(shù)可以具

21、有良好的密碼學(xué)性質(zhì).而平衡性是布爾函 數(shù)的一個重要密碼學(xué)性質(zhì)，它反映一種安全性能，也是密碼函數(shù)的設(shè)計準(zhǔn)則之一，因此，考 察具有特殊線性結(jié)構(gòu)點的平衡的旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù)既有理論意義又有應(yīng)用價值.通過對軌道以及軌道長的研究計算，許多密碼學(xué)者給出了平衡旋轉(zhuǎn)對稱布爾函數(shù)的計 數(shù)23, 24, 25, 26, 27, 28, 29, 30, 31.為了得到平衡的旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù)，需將缶個 軌道分為兩組使得每組的向量個數(shù)是2T個.如文獻(xiàn)29給出了平衡的旋轉(zhuǎn)對稱布爾函數(shù) 的精確計數(shù)：令。是如下的方程組：立御/ = 2PJ, : ，=I zi E Z,0 Zi hpi,0 i 3)均表示以全1向量為

22、泊=0,1)-類線性結(jié) 構(gòu)點的旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù).注意到定理1.1.6,定理1.1.7以及定理1.1.8對旋轉(zhuǎn)對稱布爾函數(shù)個數(shù)的計算，我們不禁 會思考：當(dāng)n取不同的數(shù)時，同時具有平衡性以及線性結(jié)構(gòu)點的旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù)能 否確定呢？基于定理1.1.6的思想，在本文的第四章中結(jié)合線性結(jié)構(gòu)點的性質(zhì)，考慮了n(n 3)取奇數(shù)和偶數(shù)時的情形.(/)當(dāng)n為奇數(shù)時，首先我們考慮了n只含有一個奇素數(shù)飽給出了具有線性結(jié)構(gòu)點的平 衡的旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù)：定理4.2.1當(dāng)n = p時（p 3且為奇素數(shù)）,則|理| = 0, （2）|邦| = 2.當(dāng)n =，時3 3且為奇素數(shù)），此時n必為奇數(shù)，與定理1

23、.1.7相比，此時有2（|理| +| 理 |） = |&（0）| + |& | 成立.在定理421的基礎(chǔ)上，將奇素數(shù)但的次數(shù)k升高，即k 2,得到如下定理：定理4.2.2當(dāng)n =夢時（但為奇素數(shù)且k 2）,貝iJ（l）|F| = 土 （，.）, （2）|玲| = 2如 與定理1.1.6相比，同是n = pk元旋轉(zhuǎn)對稱布爾函數(shù)，具咨線1 生結(jié)構(gòu)點以及平衡性旋轉(zhuǎn) 對稱布爾函數(shù)的個數(shù)比只有平衡性旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù)要少，也即|理| + |理| 2）時，則（1）|玲| = 0, （2）|理| = （口。？（2，）（H。仕） i=l頂=3論=3進(jìn)一步的，討論兩個素數(shù)的情況，得到下述兩個定理：定理4.2

24、.7當(dāng)n = 2湖寸，其中，為奇素數(shù)，貝=0, （2）|理| =立生。*%.i=l定理4.2.8當(dāng)n =紉吐其中但為奇素數(shù)，則（1）|玲| = 0,|理| = 氣0）卒皿. i=l由以上研究可看出，我們從n = pk, n = pq, n =護(hù)q, n = pqr（p, q, r為不同的素數(shù)）方面 入手，考慮了具有特殊線性結(jié)構(gòu)點的平衡旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù).特別的，對于n =夢， n = pq,當(dāng)p = 2或者但=4時（即定理4.2.6 4.2.8）,也就是說n為偶數(shù)時，此時的旋轉(zhuǎn)對稱 布爾函數(shù)有自共軸軌道，這是與n為奇數(shù)時的不同之處，因此，需要分情況進(jìn)行討論.由以上的篇幅中我們所闡述的結(jié)論的

25、側(cè)重點在于：軌道的數(shù)量性質(zhì)對有限群結(jié)構(gòu)的影 響，軌道以及軌道長對平衡旋轉(zhuǎn)對稱布爾函數(shù)個數(shù)的影響，我們的工作也在這一范疇.對于 軌道這一龐大的體系而言，我們所做的工作無疑只是冰山一角，有若干重要的結(jié)果我們都 為引入，例如，彈性旋轉(zhuǎn)對稱布爾函數(shù)的構(gòu)造與計數(shù)問題（32, 33, 34, 35, 36）,以及平衡的 或趨于穩(wěn)定的旋轉(zhuǎn)對稱函數(shù)如何進(jìn)行分類的問題（如37）等等.這些問題都被人們所關(guān)注, 并且仍有大量尚未解決的問題，需要尋找新的方法，新的手段去探索未知的領(lǐng)域.1.2本文工作的意義本文的工作主要由兩大部分組成，第一部分主要考慮了有限群論中的一類特殊的軌道 共貌類，從正規(guī)子群N的兩個最長的非中心

26、G-共軸類長出發(fā)，研究了有限群的超可解性. 第二部分對理中的元素所形成的軌道以及軌道個數(shù)進(jìn)行研究，給出了同時具有平衡性以 及線性結(jié)構(gòu)點的旋轉(zhuǎn)對稱布爾函數(shù)的計數(shù).從上述研究可以看出，軌道在不同的研究領(lǐng)域都有極為重要的地位.在有限群中，當(dāng) 共軸類具有不同的數(shù)量性質(zhì)時，有限群的結(jié)構(gòu)可能發(fā)生變化.于是這就促使我們尋求更多 的數(shù)量性質(zhì)去探索有限群的結(jié)構(gòu).本文第三部分進(jìn)一步豐富了有限群結(jié)構(gòu)的相關(guān)研究.另 外，我們利用軌道研究布爾函數(shù)的性質(zhì)時，需對軌道長以及軌道個數(shù)進(jìn)行研究，根據(jù)布爾函 數(shù)的平衡性（或相關(guān)免疫性、彈性等）給出相應(yīng)的方程組，通過解方程組從而求出旋轉(zhuǎn)對稱 布爾函數(shù)的個數(shù).不僅豐富了密碼學(xué)中對旋轉(zhuǎn)

27、對稱布爾函數(shù)的相關(guān)研究與應(yīng)用，這更便于 密碼學(xué)工作者尋找具有良好密碼學(xué)性質(zhì)的旋轉(zhuǎn)對稱布爾函數(shù).1.3有待解決的問題通過對軌道以及軌道長的計算，我們分別給出了當(dāng)n = pk, n = pq, n =護(hù)q, n = pqT（p,q,r為不同的素數(shù)）時，具有特殊線性結(jié)構(gòu)點的平衡旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù).那么 當(dāng)n = pklqk2（ki, k2 6 Z）以及n =夢加舟（幻,做晶e Z）時，具有特殊線性結(jié)構(gòu)點的平衡旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù)能否確定呢?第二章預(yù)備知識作為本章的準(zhǔn)備工作，在此主要介紹一些基本概念和重要結(jié)論，這些概念和結(jié)論在后 面的章節(jié)中都會被反復(fù)引用.2.1基本群論知識定義2.1.1設(shè)G為群

28、，對于G中的兩個元素a和們?nèi)绻嬖贕中的一個元素g,滿足 g-】ag =如我們稱a和供軸.很容易證明共軸是等價關(guān)系，因此將G分割為等價類.包含元 素a屬于G的等價類是a。= Bag : g G，并稱為a的共軸類.a的共軸類中元素的個數(shù) 稱為a的共軸類長度(簡稱類長).若CG(a)代表G中的a的中心化子，即所有滿足ag = ga的 元素g所組成的子群，則指數(shù)|G ： CG(a)|等于元素a的共軸類長.定義2.1.2網(wǎng)若群G存在主群列1 = Go Gl 辦=G使得該列的每個主因子 是素數(shù)階循環(huán)群，則稱G是超可解群.明顯地，由這個定義，超可解群的子群和商群仍為超可解群，超可解群的直積仍為超 可解群.

29、定義2.1.3 我們稱一個群G是quasi-Frobenius,如果GZ(G)是一個Frobenius,這 里7(G)是群G的中心.2.2基本密碼學(xué)知識旋轉(zhuǎn)對稱布爾函數(shù)是密碼學(xué)中的布爾函數(shù)的一個重要子類，自1999年，Pieprzyk等提 出了它在快速實現(xiàn)的Hash算法中的應(yīng)用以來，這類函數(shù)就得到了學(xué)者們的廣泛關(guān)注.為方 便后續(xù)工作的敘述和引用，本部分給出布爾函數(shù)的幾個基本概念：定義2.2.1記是一個二元域0,1,理為上的侃維向量空間，定義理到凡上的函 數(shù)六SC)= 3), X =(Ti, T2, - ,Xn) E理為72元布爾函數(shù).定義/的支撐集為supp(f) = x e f(x) = 1

30、,稱支撐集所含元素的個數(shù)為/(%)的漢明重量，記 為對于任意一個集合4,用|4|表示集合4內(nèi)元素的個數(shù).若wt(f) = supp(f)2i,則稱/(時是平衡函數(shù).若將。到2” - 1之間的整數(shù)N表示成二進(jìn)制數(shù)(中,叼，xn),則可將從0到2” - 1之間 的整數(shù)和羽上的向量一一對應(yīng)起來，即N I(T1,叼，Tn)整數(shù)從小到大剛好對應(yīng)理中元素按字典序從小到大.對于一般的n元布爾函數(shù)六z)最基本 的表示方法是通過長為2的真值表表示：或者(/(0,0,. ,0),/(1,0,. ,0),/(0,1,. ,0),/(!,1,- ,0),/(1,1, ,!)定義2.2.2設(shè)n為正整數(shù)，對任意的(%1,

31、叼,，如)G F?和1 k n,定義p*(z2, ，減=(P*1)，P*2)，P” 崩),其中 Pn(Xi)=X(i+k)mod n-設(shè) se = (ti, , xn) e令 Gn(x) = pf(%) | 1 /c n表示由向量 a?生成的軌道，由于Gn(x)中每個向量的重量都相等，定義軌道的重量為該軌道中向量的漢明重量. n元RSBF的軌道個數(shù)為 2相，其中，外)為歐拉函數(shù)閔.kn我們知道n元布爾函數(shù)共有2”個向量，可將每個向量按照上述定義進(jìn)行旋轉(zhuǎn)，經(jīng)過旋轉(zhuǎn) 后可得到相應(yīng)的軌道.以n = 4為例，給出理的所有軌道.首先給出理中的所有元素：(0,0, 0,0), (1,0,0,0), (0,

32、1, 0,0), (0,0,1,0), (0,0,0,1), (1,1, 0,0), (1,0,0,1), (0,0,1,1), (0,1,1, 0),(1, 0,1, 0), (0,1,0,1),(1,1,1, 0),(1,1, 0,1),(1,0,1,1), (0,1,1,1),(1,1,1,1) 下面根據(jù)定義222給出理的所有軌道：p(o, 0,0, 0) = P 弘 0, 0, 0, 0) = pj(o, 0,0,0) = pf (0,0,0, 0) = (0,0, 0, 0)所以由(0, 0, 0, 0)生成的軌道為(0,0, 0,0)p(i, 0,0, 0) = (0,1, 0,

33、0), p：(l, 0, 0,0) = (0, 0,1,0)pj(l, 0,0, 0) = (0, 0, 0,1),團(tuán)(1, 0, 0,0) = (1, 0,0,0)那么由(1, 0, 0, 0)生成的軌道為(1, 0,0,0),(0,1,0, 0),(0, 0,1, 0),(0, 0,0,1)第二章預(yù)備知識(1,1,0,0) = (0,1,1,0), 2(1,1,0,0) = (0, 0,1,1)pj(l, 1,0, 0) = (1, 0, 0,1),團(tuán)(1,1, 0,0) = (1,1,0,0) 那么由(1, 1, 0, 0)生成的軌道為(1,1,0,0),(0,1,1, 0),(0, 0

34、,1,1),(1, 0,0,1)pi(l, 0,1, 0) = p*(l, 0,1, 0) = (0,1, 0,1), p：(l, 0,1,0) = pS(l, 0,1, 0) = (1, 0,1, 0) 那么由(1, 0, 1, 0)生成的軌道是(1,0,1,0), (0,1,0,1)p(i, 1,1,0)=(0,1,1,1), p3(i, 1,1,0)= (1,0,1,1)屋(1,1,1,0) = (1,1, 0,1), (1,1,1,0) = (1,1,1,0) 那么由(1, 1, 1, 0)生成的軌道為(0,1,1,1),(1,0,1,1),(1,1, 0,1),(1,1,1,0)p(

35、l, 1,1,1) = p7(1, 1,1,1) = pj(l, 1,1,1) = pi(l, 1,1,1) = (1,1,1,1) 那么由(1,1,1,1)生成的軌道為(1,1,1,1)定義 2.2.3 9如果對任意的(Z2, , Tn) e F21 都有/(pf(/l，叼，崩)= -，崩,其中1 k 2),記= x x e Fw(x) = , IV2 中向 量的周期是n = 2的一個因子，也即所有向量的周期均在集合2小| 1 m內(nèi).用& 表示在附敏中周期為2隊的向量組成的集合,lm3時，4 m中自共桁軌道的個數(shù)為22f m定義2.2.5 9設(shè)/ e Bn,向量。e理 稱為布爾函數(shù)/的線性結(jié)

36、構(gòu)點當(dāng)且僅當(dāng)/( + a) + /(a?)為常值.若/(? + ) + /(sc) = 0,則稱CU為y的0-類線性結(jié)構(gòu)點；若/(03 + a) + /(03)= 1,則稱Q! 為/的1-類線性結(jié)構(gòu)點.記&(。) = f Bn I /(a?) + /(a? + 1) = 0;尺2(1) = (/ E Bn | /(a?) + /(a? + 1) = 1.為方便讀者，我們約定以下記號：理=州I球e時0）且函（州）=2“i；玲=房I此e孩且踞也）=2“i.第三章關(guān)于最大G-共軸類長的數(shù)量性質(zhì)在有限群論中，我們研究了一類特殊的軌道一共貌類.本章利用共軸類的數(shù)量性質(zhì), 著重研究了正規(guī)子群N的兩個最長的

37、非中心G-共輒類長的數(shù)量性質(zhì)對有限群超可解性的 影響.下面我們介紹本章用到的主要引理.3.1關(guān)于共軸類長的一些主要引理引理3.1.1.回設(shè)N是有限群G的一個正規(guī)子群，z是G的一個元素.那么；()xN 整除()|(Mr)G/“整除|科引理3.1.2.【11設(shè)N是有限群G的一個正規(guī)子群，b, c e N,令B = bG,C = cG,且(|劇, |C|) = 1.那么；()G = Cg(0Cg(c);()BC =。3是入的一個G-共柄類且切C|整除|B|C|.引理3.1.3.同設(shè)A是有限群G的一個正規(guī)子群，是N的一個最長的非中心G-共柄類 且切=m,則有下列結(jié)論成立；令C是N的一個G-共輛類且(|

38、晶|, C) = 1,那么| n, (m, n) = 1,。是N的一 個G-共輒類且D 1.如果(|。|, n) = 1,那么|。| = m.引理3.1.4.同設(shè)N是有限群G的一個正規(guī)子群，令晶是N的一個最長的非中心G-共瓶 類.令M =。|。是N的一個G-共姬類且(|。|, |晶|) = 1)那么M是一個交換群.進(jìn)一步，如果(Z(G) nAr) |aG| = n是N的兩個 最長的非中心G-共輒類長且(m, n) = 1,如果m無平方因子，那么NZ(N)或者是一個素 數(shù)寤階群或者；對任意的z E N, |提| = 1, |a|或者礦|;N/Z(N)是一個以交換群Cn(o)/Z(N)為核,交換群

39、CN(b)Z(N)為補的可解的 Frobenius 群.3.2主要結(jié)果定理3.2.1 設(shè)G是一個有限群，N是G的一個正規(guī)子群.設(shè)a, b e N, |6G| = m, |aG| = n. 假設(shè)772 n是N的兩個最長的非中心G-共姬類長，滿足(772,71) = 1且772, 71均無平方因子, 那么N超可解.如果N/Z(N)不是一個素數(shù)幕階群，那么NZ(N)是一個Frobenius群.證明：令M =是N的一個G-共貌類，且(|O|, m) = 1)設(shè)N是一個極小階反例.我們將分以下步驟來進(jìn)行證明：步驟 1.如果Z e Z(Cg0) nN,那么Z e Z(G)或CG(x) = CG(b).顯然

40、，由 z e Z(Cg (b)可得 Cg (b) CG(X).如果 z Z(G),則 |理| m,所以(H, n) = 1.由引理3.1.3矢口&| = m,即Cg(z) = CG(b).步驟2.我們可以假設(shè)b是一個素數(shù)幕階元，設(shè)為質(zhì)元.設(shè)p為o(b)的一素因子，bp為b的p-部分，且C*G(bp) + G .那么C.(b) = C.(bpbp/) = C*g(6p) A C*g(婦) *(bp)所以bpeZ(CG(b)nN又因如車Z(G),由步驟1知Cg(6) = CG(bp).因此，我們可以假設(shè)b為p-元.步驟3. CnQ) = P xL,其中尸是CN(b)的SgZow但-子群，L是*也)

41、的p-Hall子群, 且 Z(Cg(.如果 條 7(G),貝WnW Z(CG(b).對任意的衫-元e CN(b),有Cg伽)=CG(b) n Cg(司 CG(b)則所|伽)G|.由臚|的極大性有bG=(bx)G,即CG(bx) = CG(b) CG(x)所以e Z(CG(b),所以p-Hall子群存在，設(shè)為，即刀 Z(Cg*).則CN(b)=P x 其 中P為CnQ)的SgZo% p-子群，刀是*的p-Hall子群，且L Z(CG(b).特別地，如果A條Z(G),饑e L是一個非中心g-元.由步驟1有Cg(V)= CG(b),從 而Cn3) = Cn0),所以Gv(g) = Q x Lq,其中

42、Q為Cn3)的S訊ow q-子群，弟是*(g) (從而也是C*)的q-Hall子群，且兒 Z(CG(b).注意到。傳)=LLq,其中L Z(CG(b) Lq Z(Cg(6)所以，C) M Z(Cg(.步驟4. p m.否貝lj,我們pn= |aG|.由引理3.1.1有,彳|挪|.又由引理3.1.2知N = CN(a)CN(b), 所以|抄| = N : )| = |$(a) : *(a)| = CN(b) : *(a) C )|所以Gv(a) E Ov(b)包含。n(6)的一個Sy low p-子群.那么從而F CN(a),即*(a)包含*(6)的一個Sy low但-子群.所以我們有b e P

43、 *(a),所 以 becg.如果多Z(G),因為a e C*),由步驟3知Cg(6) CG(a),那么| | |,矛盾.如果L Z(G),即乙中的元素可以和G中的任意元素可交換，從而L中的元素可以和a 交換，所以 ).又因P 6(a),因此有方 。心,Mlal | bN.因|, bG) = 1,由引理3.1.1 知|a”=l,即N = CN(a).因為a E CN(b)=P x L顯然我們可假設(shè)a為但-元 對每一個但-元；r e N = Cn(cl),有C.(ax) = CG(a) n CG(x) CG(a)那么|療 | |(az)G|,所以|(az)G|=n.又由CG(ax) C&(a)知

44、CG(ax) = CG(a),因此CG(ax) = C*G(a) Cg(z)則有t e Z(&(a) = Z(N)當(dāng)然我們有z e Cn(0,所以Z e L,即*(a)的”部分均包含在中.所以N/N n Z(G)為代 群，從而N/N A Z(G)為超可解群.又因N A Z(G) ) = Ca(ap) E Cq(ap) Cg(%)所以1球| | |婦,貝!(|a?|, m) = 1,由M的定義有 e M.如果 Z(G),由引理3.1.4有p G 7T(MAVnZ(G) C 7T(m)矛盾.所以a, 6 Z(G),則Cg(q) = CG(apdp，) = CG(Qp/)因此，我們可以假設(shè)a為元.步

45、驟6. CN(a)p Z(G)P.假設(shè)存在一個非中心元?/ 6 Cn(cl),則C.(ay) = CG(a) n CG(y) CG(a)由定理 1 的假設(shè)，有CG(ay) = C*G(a),即|(ag)G| = aG,從而(|(匆)仁|, m) = 1,即ag G M. 因為a M,所以g M.又因為g是*(a)的但-元，且?/ Z(G),所以p E +(MjN n Z(G) C 7r(m)與步驟4矛盾，所以CN(a)p Z(G)P.步驟7. 6(a) C CN(b) Z(G),且Z(G)nN = Z(N).如果存在非中心元?/ e cN(a) n CnQ),下面分兩種情況討論：當(dāng) Z(G)時

46、，因為g G CnQ),那么我們可以假設(shè)g是但-元，則；6 CN(a)p,則由步 驟6知g e Z(G)p,矛盾.當(dāng)L幺Z(G)時，由步驟3知y e eg Z(CG(b)那么由步驟1知C*G(g) = Cg(6),從而Gv(0)= CnQ),所以Q e *(?/) = Cn8) Z(Cc(b) 從而Cg(6) Cg(o), M|aG| | bG,矛盾.由以上討論知Cjv(a) C CnQ) Z(G)進(jìn)而CN(a) n CN(b) Z(G) n N又因Z(N) CnS) Z(N) CnQ)所以Z(N) Cn(o) n CN(b),因此Z(N) Z(G) A N.又顯然有Z(G) n N |aG|

47、 = n是G的兩個最長的非中心共猊類 長，滿足(m,n) = 1且m, n均無平方因子，那么G超可解.特別地，如果GZ(G)不是素數(shù)驀 階群，那么G/Z(G)是Frobenius群.證 令N = G.顯然，N滿足定理3.2.1的假設(shè).因此，根據(jù)定理3.2.1, N = G是超可解 的.如果G/Z(G)不是素數(shù)幕階群，那么GZ(G)是Frobemus群.第四章兩類具有特殊線性結(jié)構(gòu)點的平衡旋轉(zhuǎn)對稱函數(shù)的計數(shù)作為軌道數(shù)量性質(zhì)的應(yīng)用，我們研究了同時具有特殊線性結(jié)構(gòu)點以及平衡性的旋轉(zhuǎn)對 稱布爾函數(shù)的計數(shù)問題，得到了一些新的結(jié)果.下面介紹本章用到的主要引理.4.1主要引理引理4.1.1. 9設(shè)n是偶數(shù)，且

48、r I n,則理 中圈長為廣的所有自共柄軌道個數(shù)為sn(r) = i2r/2 - tsn(t)tr/2,tr/2那么理中自共瓶軌道的個數(shù)為= s”(r).rn引理4.1.2.【9若九是偶數(shù)，則|&(0)| = 2(如+s”)/2, |&| =0.其中|尺= o, 1)表示以全I(xiàn)向量為今-類線性結(jié)構(gòu)點的旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù).對于n元布爾函數(shù)，若令知為所有含d(其中d | n)個向量的軌道個數(shù)，文獻(xiàn)30給出了如 下定理：i i 1引理4.1.3. 3。令侃=砰(p為素數(shù)),那么九1 = 2, hpi = 2-(1 i r 1)7 hpr = pr(2pr + eipW ) hpi 2.j=ij=

49、i 方便起見，我們令饑為所有含個向量的軌道對數(shù)，顯然d是n的因子，且滿足如=% 當(dāng)n為奇數(shù)時，有2饑=gn.當(dāng)n為偶數(shù)時，有 + 2饑=gn.由于當(dāng)n 3.4.2主要結(jié)果在本章中結(jié)合線性結(jié)構(gòu)點的性質(zhì)，考慮了n(n 3)取奇數(shù)和偶數(shù)時具有特殊線性結(jié)構(gòu)點的平衡旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù).(I)當(dāng)n為奇數(shù)時，首先我們考慮了n只含有一個奇素數(shù)，的情形：定理4.2.1當(dāng)n = p(p 3且為奇素數(shù))時，則|理| = 0, (2)|理| = 2/ 證明：(1)首先證明|理| =0.因為n為奇素數(shù)，則對任意的e理,有Gn(x)nGn(x+l) = 0,即G”(時與辦(+1)總 成對出現(xiàn).那么對任意的州e Rn(

50、0),有州(時和州(刀+ 1)同時為0或者同時為1.當(dāng)n = p時,有11 = 1,上=尊蘭再由軌道個數(shù)計算公式可得gp = tEk).W = ikp從而Zp =氣因為州為平衡函數(shù)，所以我們從長為1和但的軌道中分別選。對,Z對,使得所 取的軌道所包含的所有向量a；共有2P-1個且滿足/() =0,剩下的2PT個向量仲滿足/(時= 1,即滿足下列方程：2y2pz = 2p 其中f 0 ?/ 1;0z 3且為奇素數(shù))時，有|理| = 0, |玲| = 2*2.例4.2.1:我們以但=5為例，計算庵|和庵|.當(dāng)?shù)?5時，我們將其所有元素列出如下：(0,0,0,0,。)(1,1,1,1,1)(0,0,

51、0, 0,1),(0, 0, 0,1,0),(0,0,1, 0, 0),(0,1,0,0,0),(1, 0, 0, 0, 0)(1,1,1,1, 0),(1,1,1,0,1), (1,1, 0,1,1), (1,0,1,1,1),(0,1,1,1,1)(0,0,0,1,1),(0, 0,1,1,0), (0,1,1,0,0),(1,1,0,0,0), (1,0, 0,0,1)(1,1,1,0, 0),(1,1,0,0,1), (1,0, 0,1,1),(0, 0,1,1,1), (0,1,1,1,0)(0,0,1,0,1),(0,1,0,1,0), (1,0,1,0, 0),(0,1,0,0,

52、1), (1,0, 0,1,0)(1,1,0,1, 0),(1, 0,1,0,1), (0,1, 0,1,1),(1, 0,1,1,0), (0,1,1,0,1)首先我們計算I理|.當(dāng)n = 5吐虹=1, /5 = 3,我們從中分別取出；對，Z對，由定理4.2.1可得方程：2g + 2 x 5z = 25-1,其中f 0 ?/ 1;0 3.即g + 5z = 8,其中 0 ?/l,0z 2,得到如下定理：定理4.2.2當(dāng)n=pk(p為奇素數(shù)且k 2)時，則|理| = E(n C*), (2)|邦| = 2如i=i i=i pZ七 R證明：(1)首先證明曜=宥(業(yè)世)因為P為奇素數(shù)，則對荏蓄S富

53、e理,Gn(x)與Gn(x + 1)總成對出現(xiàn).那么對任意 的州 &(0),有州()和f(x + 1)同時為0或者同時為1.當(dāng)n =夢時，由引理4.1.3有：OI-L 11 = 1,上=峙=寧,農(nóng)=寧=坦，.，=因為州為平衡函數(shù)，我們從長為1, p, p2, , 7/的軌道中分別選I/O對，？/1對，？/2對，,弘對, 使得所取的軌道所包含的所有向量共有2伊t個且滿足f(x) = 0,剩下的2p*t個向量滿 足六時=1,即滿足下列方程：f W* = 2伊 t；i=0設(shè)上述方程有匕組不同的解，其中MKI 2z)組解為：(疏M，疝 從而可知：ii = f(n 2)時,有I理I = E(n c),

54、I理I = 2/ 1=1 i=l pt例4.2.2:我們以n = 52 = 25為例，計算|理|和成赤|.首先我們計算仔& I.當(dāng)n = 25時,則有Zi = 1, 15 = 3, Z25 = 671088.我們從中分別取出?/對，z對,r對,由定 理4.2.2可得方程：2g + 2 x 5z + 2 x 25r = 225-1,其中0 ?/ 1； 0 3;0 r 671088.上述方程等價于：g + 5z + 25r = 223由g, z的取值范圍可知0 ?/ + 5z 16也即0 223 - 25r 16因為r為正整數(shù)，解得r = 335544,此時?/ + 5z = 8,又由?/, z取

55、值范圍，顯然，此方程組無解. 即不存在g, z, r使得：2g + 2 x 5z + 2 x 25r = 225-1所以I璃=0.下面計算I死八因為房為平衡函數(shù)，此時。25(時與。25(% + 1)恰有一個屬于房的支撐集因此，我們 只需令每對軌道中的任一條屬于龍5的支撐集即可由軌道計算公式可知：925 = &0(1) 225 + 0(5) 25 + (25) 2) = 1342184所以當(dāng)n = 25時，有671092對軌道，每對軌道有2種選擇，從而|死= 2。 = 2671092.下面利用定理4.2.2,給出部分疣元的|理|和任；|.表3 n=9, 25, 49時，|理|和舊；|的取值nhI

56、pZp2gj2時191128300230251367108867109202671092491957443872798085744387279818025744387279818定理421和定理422討論了只含有一個素數(shù)的情況，我們將素數(shù)個數(shù)增加，考慮兩個 奇素數(shù)的情況，具有線性結(jié)構(gòu)點以及平衡性旋轉(zhuǎn)對稱布爾函數(shù)的個數(shù)能否給出呢？下述定 理給予了回答：定理4.2.3當(dāng)n=pq(p,q為互異的奇素數(shù))時，則|理| = 2如(2)|理| =五空代吒. i=l證明：(1)我們不妨設(shè)？ _1+1 _ 2 p ，Gq 2 q )Cpq 2pq-州為平衡函數(shù)，我們在長為1, p, q,軌道中分別取go對，弟

57、對，對，？/：3對，使得：2go + 2物 1 + 2qy2 + 2pqys = 2P9-1,其中0 ?/o 11；0 ?/i Ip；0 ?/2 lq；。M ?/：3 V Ipq.設(shè)上述方程組有匕組不同的解，其中第2（1 2 t）組解為：（姑，亦說，必.從而可知：|理| =立圮以泛.i=l由以上討論可知，當(dāng)n = pq（p,q為互異的奇素數(shù)）吐則有|理| = 說，I玲 1 = 2如I例4.2.3:我們以n = 15為例，計算|理|和廚5.首先計算招.因為15為奇數(shù)，所以GM%）與。15（% + 1）成對出現(xiàn).又侏e R15為平衡函數(shù)，那么我 們只需令每對軌道中的其中任意一條屬于片5的支撐集即可

58、當(dāng)n = 15時，共有零=1096對 軌道，由定理4.2.3（1）可知|F招=2】96.下面計算|理|.當(dāng)n = 15時，我們從長為1, 3, 5, 15的軌道中分別取出必寸,z對,廣對,幻對，由定理4.2.3可 得方程：2g + 2x3z + 2x5r + 2x 15w = 215-1,其中（o ?/ 1；0 1;0 r 3;0 w 1091.上述方程等價于：g + 3z + 5r = 213 15w由g, z,的取值范圍可知0 ； + 3z + 5r 19 所以0 213 - 15w 19又迎為正整數(shù)，可得b G 景，警=545,546.當(dāng)踞=545時，g + 3z + 5r = 213

59、15w = 17,又由g, z, r的取值范圍，顯然此方程 組無解；當(dāng)彩=546時，g + 3z + 5r = 213 - 15w = 2,又由g, z, r的取值范圍，顯然此方程 組仍無解.也就是說，不存在g, z, t,叫使得：2g + 2x3z + 2x5r + 2x 15w = 215-1所以I理I =0.下面利用定理4.2.3,給出部分元的|理|和F：|.表2 n=15, 21, 33, 35時，|理|和|玲|的取值nhIplqIpqg2l/,?ln15113109110960210962111949929499400249940331193130150493130150588021

60、3015058835139490853403490853416-1 0/2/245426701loou4908534032490853416特別的，對于含有兩個奇素數(shù)時，我們將其中一個奇素數(shù)但的次數(shù)升高至2,得到了： 定理4.2.4當(dāng)n = p2g(p, q為互異奇素數(shù))時，貝!1|玲| = 2”,|理| = f洗理代伏代遢證明：首先證明I尺I =2血2.因為飽q為奇素數(shù)，此時乃仍為奇數(shù)，所以Gn(ie)與Gn(x + 1)成對出現(xiàn)，那么對于孑；e Rn(l)為平衡函數(shù)，由定理421(2)討論可知|玲| =2如下面證明|理| =亳0扣*。計。如當(dāng)n =疣q時，其軌道長只可能為1, p, q,