资源描述：
《算法合集之《置换群快速幂运算_研究与探讨》.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、置换群快速幕运算研究与探讨江苏省苏州中学潘震皓［关键词］置换循环分裂合并［摘要］群是一个古老的数学分支，近几年来在程序设计中置换群得到了一定的应用。本文针对置换群的特点提出了线性时间的幕运算算法，并举例说明了优化后算法的效果。［正文］一、引言置换群是一种优秀的结构，在程序设计屮，它的大部分基木操作，时间和空间复杂度都是线性的，共至有的还是常数的。所以一个问题如果能够抽象归结为一个置换群模型的话,往往能够在稈序设计屮轻松地解决。但是对于報幕运算来说，似乎只能通过反复做乘法来获得0(k*乘法)或是0(lo
2、gk*乘法)的算法；而对于分数幕运算，则找不到较好的方法实现。二、置换群的整慕运算2.1?幕运算的一个转化在置换群中有一个定理：设7**(T为一置换，e为单位置换(映射函数为f(x)=x的置换))，那么k的战小正桀数解是T的拆分的所有循环长度的最小公倍数。或者有个更一般的结论：设Tk=e,(T为一循环，e为单位置换)，那么k的最小正整数解为T的长度。我们知道，单位置换就是若干个卩含甲个兀黍也脩号、的并。也就是说，长度为1的循环，1次的幫，把所有元素都完全分裂了。这是为什么呢？我们来做一个试验：(下面的
3、置换均以循环的连接表示)设门二6,那么T6=(T2)任取一T=(l35246),来做一遍乘法：T2=仃23456〕‘123456]45621丿4562‘123456〕‘34562.34562L<562143,仃23456、<562143丿=(>54X263)分裂成了2份！而且这2份恰好是T的奇数项和偶数项！(注意可以写成(154)(326))再来看看ThT3=T2T‘123456、‘123456、一、562143,k345621?‘123456、‘562143、一、562143丿‘123456、一、
4、214365丿14365丿=(12X34X56)不出所料，分裂成了3份，每份分别是在原来循环中的位置mod3-0,1,2的项。继续看厂：T4―卩2卩2"23456、‘123456、<562143；,562143’"23456、V62143、Q62143丿、436512丿了123456、<436512；-(145)(236)与前面不同的是，循环只分裂成了2份。并且每一份的循环看起来都是杂乱无章的，只知道是在循环中的奇数项和偶数项。再来拿做个试验：T5—T-T3<123456〕23456〕<56214,2
5、14365丿<123456]62143、<562143丿351234><123456]<651234丿=(164253)这次的循环，根木没有分裂，只是顺序改变了一下。这之间有什么共同点呢?对，那就是gcd(k,l)o因为gcd(6,6)=6,所以循环会完全分裂,而gcd(2,6)=2,gcd(3,6)=3,gcd(4,6)=2,gcd(5,6)=1也相对应了上面的每一个试验的结果。经过多次试验以后，我们得到三个结论：结论一：一个长度为1的循环T,1是k的倍数，则〃是k个循环的乘积，每个循环分别是循环T
6、屮下标imodk二0,1,2…的元索按顺序的连接。结论二：一个长度为1的循环T,gcd(l,k)二1,则7^是一个循环，与循环T不一定相同。结论三:一个长度为1的循环T,戸是gccKl,k)个循环的乘积,每个循环分别是循环T中下标imodgcd(l,k)=0,1,2…的元素的连接。可以看出，结论三只不过是把k分成gcd(l,k)*(l/gcd(l,k)),再运用结论一和结论二所得到的。如果这几个结论是正确的话，那显然只需要确定结论二中叙述的〃，就能够在0(n)内解决任意循环的任意報幕运算了。2.2循环
7、长度与指数互质时的整幕运算和上面一样，我们来做几个试验。设T二(12534),则:2354235445Y145Y22345、5413丿5413、124丿45>2*23)U2<53厂12J3345YI2345Y53345、413,124、51,_123一、531=(154不知大家有没有注意到，如果把循环T的奇数项和偶数项取出来，就是154和23,如果两者并在一起，就是刚才求出的T2To再试一个：T3=T2T45]5I45)_I23~,342=(132同样地，把mod3=1,2,0的项取出来：13、24、
8、5,连接在一起，就是所求得的新循环To把这一试验结果写成一个定理，就是:设a=T,a^=Tk,且gcd(l,k)=l,则a^[i]=a[伙+l)imod/]。这个定理看起来似乎挺复杂，但如果曲张图看，一点也不复杂:设1=10,k=3：像这样反复前进三格，然后涂色最示,得到的循环就是所需要求的Tk了。证明：设任意0<能唯一地找到a[t]=j,a'[s]=j.那么j-T显然等于4(^+l)mod/7],j^YT=a[(t+p)modn]((t)〃T表示连续执
