群元素阶的系统分析及其应用*

2014-03-30姚俊萍李新社

哈尔滨师范大学自然科学学报 2014年4期

姚俊萍，李新社

(西安高新技术研究所)

0 引言

由文献［1-5］可以看到元素的阶对于群的重要性.元素的阶是群论中最基本的一个概念.从著名的Burnside问题可以看出，元素的阶在群的结构中起着重要的作用.群中元素的阶是一个基本的数量.如果把群看作一个整体，其中的元素就是一个局部，局部和整体有着密不可分的联系.为此，考察元素阶的作用，可使从局部来看整体，并推导和引申各种不同群的性质，进而促进计算机科学和算子理论的应用与研究.

1 群元素阶定义

设G为群，a∈G且e是G的么元时，使an=e成立的最小正整数n称为元素a的阶，记为|a|=n.若这样的n不存在，则称元素a的阶为无限(或为零).

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

(2)在整数加群〈Ⅰ，+〉中，因为0是么元，任意整数a的任何正整数幂均不为零，所以只有0的阶为1，其余整数的阶皆为无限(或零).

2 元素阶的性质

许多著名教材中都有关于群元素阶的性质论述，但都比较简单，缺乏系统性，这里借鉴文献和编著就一些特别需要关注而且应用较多的性质及其结论予以分析研究讨论.

(1)在有限群中，每个元素的阶均有限.这是因为若某个元素b的阶为无限，那么对于任何正整数i和j，必有i≠j当且仅当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)设群G中元素a的阶为n，则|ak|=因为(ak=e，所以，不妨设，如此则有，但an=e且|a|=n，故，因此t=1，从而成立.由此立即可以得出|ak|=1⇔(k，n)=1，其中k为任意整数.

(3)在群G中，若|a|=m，|b|=n，(m，n)=1，ab=ba则|ab|=mn.由(ab)mn=amnbmn=e知|ab||mn，不妨设，如此则有或t|n.当t|m时，进而，所以t|n;类似地当t|n时有t|m，但(m，n)=1，因此t=1，故|ab|=mn成立.

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

(4)设n是交换群G中所有元素的最大阶，则G中每个元素x的阶都是n的因数［6］，于是xn=e.

假设交换群G中元素a的阶为n，且达到最大.对于任意元素x，不妨设|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)设G是群，a，b∈G，则ab与ba同阶.

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

(7)在群G中，设|a|=n，r是任一整数，若(n，r)=d，则(ar)=(ad).

(8)设p，q是互异素数，|G|=pq，G是可交换群，则G是循环群.

因为群G是pq阶可交换群，显然G中至少有一个周期为p或q的元，不妨设a是G中周期为p的元，令H=(a)，则H是G的p阶不变子群，商群G/H是q阶群.设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)是循环群.若为q，则G=(ab)是循环群.

(9)设G是一个群，a与b的阶分别为m，n，ab=ba，则元素ab的阶是［m，n］的约数且G中存在阶是［m，n］的元素.

(10)若群G的元素a的阶有限，元素b的阶无限，ab=ba，则ab是无限阶元素.

3 元素阶与典型群的关系

(1)在群G中，若a∈G，e是G的么元，|a|=n，则{a，a2，a3，…，an}是G的子群.{a，a2，a3，…，an}关于G中运算构成子独异点是显然的.此外，对于任意的元素x=ai∈{a，a2，a3，…，an}，|ai|=，于是x-1=因此{a，a2，a3，…，an}是G的子群.这里需要注意的是，若|G|=m，则由拉格朗日定理有n|m.

(2)一个素数阶群G肯定是循环群.因为在该群中，肯定存在非单位元素a，其阶是有限的，于是|a|/|G|，然而|G|是素数，所以|a|=|G|，因此素数阶群G可以表示为{a，a2，a3，…，，故G定是循环群.

(3)根据循环群的定义，任意循环群G的阶由其生成元决定，而且循环群G的子群S肯定是循环群.假设G={a，a2，a3，…}，再设ik=min{is|is＞0}，若S中任意元素的幂是ik倍数，那么S是循环群.否则假设S中存在元素x的幂ip不是ik倍数，那么ip=qik+r，0＜r＜ik，于是，但G，而这与ik=min{is|is＞0}相矛盾，故S是循环群.

(4)设G是交换群，那么G的所有有限阶元素的集合H关于G的运算是G的不变子群(正规子群).假设a∈H，b∈H，因为G可交换，a和b的阶均有限，所以|ab|≤［|a|，|b|］，也有限，即ab∈H;又因为a-1与a同阶，也就是说a-1∈H;所以H是G的子群，再根据交换群的子群都是正规子群，可得H关于G的运算是G的不变子群(正规子群).

4 元素阶与数模之间的关系

模m剩余类关于乘法运算×m构成的代数通常不是群，但一个元素a若与模m互素，则该元素存在逆元，其阶定义为使an≡1 modm成立的最小正整数n，记为δm(a).δm(a)不但具有与群元素阶类似的性质，而且根据欧拉定理还具有下面两条重要性质.

(1)若m＞1，(a，m)=1，则aφ(m)≡1 modm，于是δm(a)/φ(m).特别地，若m=p为素数，δm(a)/(p-1).注意这里的φ(m)就是m的欧拉函数值.

(2)若(m，n)=1，(a，mn)=1，则δmn(a)=［δm(a)，δn(a)］.这个结论易由(1)得出.

事实上，数论里关于元素阶的讨论与群中方法完全一致，只不过应用在整个整数范围上.

5 元素阶概念在实际生活和信息安全中的运用

(1)将编号为1～52的卡片分为1～26，27～52两组，交错互相插入.则这样的交错插入重复8次后就会恢复到原来的牌序.

洗牌前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

第一次插入相当对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阶的轮换阶数都是8的因子，k阶轮换重复k的倍次后恢复原状，故结论成立.美国的研究人员认为，扑克牌洗7次最合适.

事实上，知道洗牌方法，就可写出对应的置换，于是将该置换表示成不相交轮换的乘积，求出各轮换阶的最小公倍数m，得出扑克牌在该洗牌方法下重复m次后恢复到初始状态.

(2)根据置换阶计算规律可以分析研究某种只进行置换的特殊密码黑盒

向黑盒输入一列数a1，a2，a3，…，an，观察黑盒输出结果，比如为ai1，ai2，…，ain，再将结果重新输入，再观察结果，肯定某次就恢复到最初状态，记录下这个次数.如果这样次数较少，实际上该黑盒就被可以破译了.因为根据黑盒输出结果反复迭代记录下的次数就得到向黑盒输入的初始值.

(3)在信息安全基础理论研究和运用中，大量涉及到群元素阶的性质.比如经常安全素数的使用.安全素数是一个足够大的形如2q+1的素数p，其中q也是素数，而且乘法群Z*P有四个子群:①只有数1组成的平凡子群;②仅由1和p-1组成的大小为2的子群;③一个大小为q的子群;④一个大小为2q的整个群.两个子群容易避免，第三个即为想要的子群.考虑所有能够写成另一数平方(当然要模p)的模p数集合.事实上，对于1，…，p-1中恰好有一半的数是平方数，一半是非平方数，但整个群的生成元是非平方数(如果是平方数，则它的任何次幂都不能产生非平方数，于是不能生成整个群).如何使用安全素数?选择(p，q)使得p=2q+1，并且p和q都是素数，在2，…，p-2中随机选择一个a，令g=a2(modp)，检验g≠1，且g≠p-1(否则重选)，这样产生的参数(p，q，g)适合Diffle-Helleman协议.当Alice或Bob收到的应该是g的方幂的值时，必须检查收到的这个值的确位于g生成的子群中.当且仅当rq≡1(modp)时，数r是平方数.此时也要禁止使用数1，完整的检验是r≠1且rq≡1(modp).事实上这里的关键问题是r关于模p阶，要求p足够大.