K 阶全距置换的构造和生成

《K 阶全距置换的构造和生成》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、№.3陕西科技大学学报Jun.2006Vol.24JOURNALOFSHAANXIUNIVERSITYOFSCIENCE&TECHNOLOGY·121·3文章编号:1000-5811(2006)03-0121-04k2阶全距置换的构造和生成1,32,3蒋晓云,梁常东(1.桂林师范高等专科学校数学与计算机科学系,广西桂林541001;2.钦州师范高等专科学校数学与计算机科学系,广西钦州535000;3.南京师范大学数学与计算机科学学院,江苏南京210097)摘要:全距置换具有良好的密码学性质,研究全距置换的构造问题具有重大意义。作者在文k中给出了偶数阶全距置换的两个构

2、造和n=2阶全距置换的一种特殊构造,并通过对全距置换进行变换,得到了从已有的全距置换生成一系列新的全距置换的简便而有效的方法。关键词:全距置换;全距排列;构造;中图分类号:TN918文献标识码:A0引言Dr.LothropMittental在1996年指出,从换位的角度来看,全距置换是具有良好密码学性质的置换,可被用于安全性很强的分组密码。因此,研究全距置换具有重大意义,特别是全距置换的构造问题。文献〔1〕对全距置换做了有意义的研究,给出了全距置换的若干性质,并提出了基于全距拉丁方的全距置换构造方法,文献〔2〕中举出的反例说明了这种方法不是有效可行的方法。文献〔3〕

3、研究了全距置换中元素间距离在排列上的特征,提出了全距特征排列的概念,给出了基于全距特征排列的全距置换的构造方法。然而,全距特征排列的构造问题都还未能很好的解决。到目前为止,关于全距置换理论的研究尚不成熟,还没有能构造出所有的全距置换的有效方法,全距置换的构造问题还有待进一步研究。本文将全距置换等价于全距排列来研究,提出了全距排列的分拆变换和逆变换,给出了由已知全距排列构造新的全距排列的一种新方法,从而得到了由已知全距置换构造新的全距置换的新方法。本文没有定义的概念与符号均与参考文献〔1〕和〔2〕中的意义相同,文中不再重复叙述。k12阶全距排列的构造我们通过观察得出了

4、两个特殊的全距排列。k定理1当n=2为偶数时,排列01n-12n-23n-3⋯k-2n-k+2k-1n-k+1k和0n-11n-22n-33⋯n-k+2k-2n-k+1k-1k为全距排列。相应的置换{0,1,3,⋯,2k-1,2k-2,⋯,4,2}和置换{0,2,4,⋯,2k-2,2k-1,⋯,3,1}为全距置换。例如n=8时,01726354和07162534为一个全距排列。k对于n=2,我们还得出了如下一个结论:ki(i+1)定理2若n=2为偶数时,则有x0x1x2⋯xn-2xn-1是一个全距排列,其中xi≡(modn)2(0≤i≤n-1)。j(j+1)i(i+

5、1)证明:(1)当0≤i

6、目·122·陕西科技大学学报第24卷(2)当0≤i≤n-2时,D(xi,xi+1)≡xi+1-xi(modn)≡(i+1)(modn),D(x0,x1),D(x1,x2),⋯,D(xn-2,xn-1)恰好为1,2,⋯,n-2,n-1,从而互不相同,所以x0x1x2⋯xn-2xn-1是0,1,2,⋯,n-2,n-1的一个全距排列。kk注:对于n=2ω(其中ω>1为奇数),上述定理不成立,因此上述构造是2阶全距排列的一种特殊方法。2全距置换的生成文献〔4〕提出对一个已有的全距置换实施变换,可以从一个已有的全距置换出发生成出更多的全距置换,但不易操作。我们将全距置换等价于

7、全距排列来研究,并发现了逆变换和拆分变换也可以由一个已有的全距排列生成新的全距排列。2.1线性变换完全类似文献〔4〕,我们有下列结论:〔4〕定理3若Л=a0a1a2⋯an-2an-1为全距排列,则对任意的整数C,经过平移得到的排列Л+C=x0x1x2⋯xn-2xn-1也是一个全距排列,其中xi≡ai+C(modn)(0≤i≤n-1)。〔4〕定理4若Л=a0a1a2⋯an-2an-1为全距排列,则对任意的满足(k,n)=1的整数k,有kЛ=y0y1y2⋯yn-2yn-1是一个全距排列,其中yi≡kxi(modn)(0≤i≤n-1)。由定理3和定理4可推得:推论1若