剩余类环z nz上的一致全向置换的存在性.doc

剩余类环Z_nZ上的一致全向置换的存在性()文章编号:1006-1037200704-0026-03剩余类环Z/nZ上的一致全向置换的存在性112刘秀玲,徐克舰,范修斌(),青岛266071;,北京1000493(()摘要:给出了Z/nZ上的l-全向置换的概念其中l?Z/nZ,讨论了l-全向置换的存在性、函数性质、计数,并在此基础上,给出了Z/nZ上的一致全向置换的概念,证明了n-1φ()当n>时,Z/nZ上的一致全向置换不存在。2关键词:完全映射;密码函数;l-全向置换;一致全向置换中图分类号:O156;:A置换是一类在密码算法中使用相当广泛的特殊的密码函数,对具有良好密码学性质的置换的研究一直是密码函数研究中的重要内容。,[1]但将完全映射的概念和理论用于密码学,仅始于20世纪90年代密码学界对正形置换的研究和讨论。目[2](前密码学中的完全映射有两类:一类是正形置换,一类是全向置换。基于正形置换的分组密码设计例如[3,5])SMS4等、分析的理论和技术已比较完善。文献[2]给出了剩余类环Z/nZ上的全向置换的概念,研究了全向置换的存在性以及作为密码函数时的密码学性质、构造和计数等问题。本文在文献[2]的基础上,进一步给出了Z/nZ上l-全向置换概念,研究了l-全向置换的存在性、函数性质、计数,并在此基础上,又进一3()步给出了一致全向置换的概念。当l遍历Z/nZ时,Z/nZ上的一致全向置换是否存在是本文讨论的重点。1n-φ()本文证明了当n>时,Z/nZ上的一致全向置换不存在。21Z/nZ上的l-全向置换的概念、存在性及性质首先,在文献[2]的基础上,给出以下定义:3()()设P?S,称P为Z/nZ上的l-定义1n全向置换,若ϖl?Z/nZ使得{lx+Px|x?Z/nZ}l3l()()Z/nZ},|S|==Z/nZ,对固定的l?Z/nZ,记S={P|{lx+Px|x?Z/nZ}为l-全向置换nn的个数。关于l-全向置换的存在性有如下结论:l3()S1定理Πl?Z/nZ,n?<当且仅当n是奇数。3ll()()()证明?<,则存在P?S,满足{lx]若Πl?Z/nZ,S+Px|x?Z/nZ}=Z/nZ,于是:nnn-1)(nn-1()(modnlx())+Px=?2x=0n-1n-1n-1())(n-1nn-1(())()(())lx+Px=lx+Px=()又)(n+modn,可知2|n-1,从而n是奇数。???22x=0x=0x=03()()()()()α当n是奇数时,Πl?Z/nZ,不妨令Px=lx,则lx+Px=2lx,由2l,n=1,显然{lxll()?<。+Px=2lx|x?Z/nZ}=Z/nZ,可知P?Sn,故Sn与文献[2]类似,容易证明l-全向置换有以下性质:()()()设P是Z/nZ上的l-全向置换,则对任意的c,d?Z/nZ,Pc+dx=Px+c+d也性质1是Z/nZ上的l-全向置换。-1-1()())(设P为Z/nZ上的l-全向置换,当且仅当对Πc?Z/nZ,置换c-lPx=c-lPx性质2有且仅有一个不动点。-1-1()()c?Z/nZ,置换Px=Pc-lx有且Π性质3设P