有限域上一类完全置换单项式的构造

doi:10.19665/j.issn1001-2400.2022.01.010

摘要/Abstract

摘要：

有限域上的完全置换多项式在密码学、编码学和组合设计等领域具有广泛的应用。中国在2006年公布的分组密码算法SMS4就是基于完全置换设计的。近年来,完全置换多项式被用来构造具有良好密码学性质的密码函数,并逐渐成为密码学中的一个研究热点。有限域上稀疏型的完全置换多项式具有代数形式简单和易于实现等优点,因而受到学者们的青睐。文中详细总结了有限域上完全置换单项式的已有构造,并利用有限域上置换多项式的一个有效判据构造了奇特征有限域上的一类新的完全置换单项式,丰富了完全置换单项式的结果。此外,计算了这些完全置换单项式的逆多项式。

关键词: 有限域, 完全置换单项式, 奇特征

Abstract:

Complete permutation polynomials (CPPs) over finite fields have important applications in cryptography,coding theory,and combinatorial design theory.The block cipher algorithm SMS4 published in China in 2006 is designed based on CPPs.Recently,CPPs have been used in the constructions of cryptographic functions.Thus,the construction of CPPs over finite fields has become a hot research topic in cryptography.CPPs with few terms,especially monomial CPPs over finite fields,attract people's attention due to their simple algebraic form and easy realization.In this paper,a detailed survey of the constructions of monomial CPPs is presented.Then we give a class of monomial CPPs over finite fields with an odd characteristic by using a powerful criterion for permutation polynomials.Our construction enriches the results of monomial CPPs.In addition,we also calculate the inverses of these bijective monomials.

Key words: finite fields, monomial complete permutation polynomials, odd characteristic

中图分类号:

TP309.7

黄萌濛,伍高飞. 有限域上一类完全置换单项式的构造[J]. 西安电子科技大学学报, 2022, 49(1): 102-110.

HUANG Mengmeng,WU Gaofei. New class of complete permutation monomials over finite fields[J]. Journal of Xidian University, 2022, 49(1): 102-110.

图/表 3

表1

表2

F p n上的完全置换单项式指数"

p	n	d(d^-1)
p=3	n=2	1(1),3(3),5(5)
	n=3	1(1),3(9)
	n=4	1(1),3(27),9(9),11(51),17(33),41(41),49(49)
	n=5	1(1),3(81),9(27),23(221),45(199)
	n=6	1(1),3(243),9(81),27(27),29(477),53(261),57(281),99(603),113(393) 157(677),183(183),209(209),313(521),365(365),417(625),547(547)
	n=7	1(1),3(729),9(243),27(81)
	n=8	1(1),3(2 187),9(729),27(243),81(81),83(4 347),161(2 241),321(1 921) 329(3 609),411(5 331),481(641),801(3 841),821(2 461),961(4 321) 1 067(3 363),1 121(3 201),1 281(5 121),1 313(3 937),1 441(3 041),1 601(5 761) 1 641(4 921),1 761(4 161),1 969(1 969),2 051( 3 691),2 081(4 801),2 401(5 601) 2 561(6 081),2 721(2 881),3 281(3 281),3 361(3 361),3 521(4 641),3 681(6 241) 4 001(4 481),5 249(5 249),5 281(6 401),5 441(5 921)
p	n	d(d^-1)
p=5	n=2	1(1),5(5),7(7),13(13),17(17)
	n=3	1(1),5(25),63(63)
	n=4	1(1),5(125),25(25),49(433),53(365),79(79),97(193),145(241),157(469) 209(209),289(529),313(313),337(337),385(577),391(391),521(521)
	n=5	1(1),5(625),25(125),529(1 937),569(2 273),853(1 421) 1 137(2 841),1 563(1 563),1 989(2 557)
p=7	n=2	1(1),7(7),13(37),17(17),25(25)
	n=3	1(1),7(49),55(199),115(229)
	n=4	1(1),7(343),49(49),97(1 633),151(1 351),193(1 057) 241(2 161),401(401),481(1 921),577(2 113),601(1 801) 673(1 537),721(1 681),961(1 441),1 153(2 017),1 201(1 201) 1 249(1 249),1 601(1 601)
p=11	n=2	1(1),11(11),13(37),31(31),41(41),61(61),91(91),101(101)
	n=3	1(1),11(121),191(571),267(533),381(761),771(1 261) 799(799),951(951)
	n=4	1(1),11(1 331),121(121),241(9 841),481(2 161),611(7 931) 721(6 721),961(10 801),1 201(10 081),1 441(11 521),1 681(14 161) 1 831(1 831),1 921(3 841),2 401(13 201),2 441(2 441),2 641(13 681) 2 881(8 161),2 929(2 929),3 121(4 081),3 361(4 321),3 601(5 521) 3 661(10 981),4 561(13 921),4 801(8 401),5 041(8 881),5 281(6 961) 5 491(12 811),5 761(7 921),5 857(11 713),6 001(10 561),6 241(12 001) 6 481(11 281),7 201(12 241),7 321(7 321),7 441(7 441),7 681(10 321) 8 641(12 961),9 121(13 441),9 151(9 151),9 361(9 601),9 761(9 761), 10 249(10 249),11 761(14 401),12 481(12 721)

表2

表3

F p n上已知的完全置换单项式v-1xd"

参数p,n,m,k,t,r以及v的取值范围	参考文献
任意素数p,d=1,v∈ $F p n$ \{0,-1}	[9]
p=d=3或p=d=5,v^-1=-a且a∈ $F p n *$	[9]
奇素数p,d= $p n + 1 2$ ,gcd(d,2)=1,η(v²-1)=1	[9]
素数p,t为正整数,若p=2,gcd(t,n)≠1,则d=2^t;若p≠2,则d=p^t,v∈ $F p n$	[19]
任意素数p,n=n₁n₂r,n₁是p在Z/rZ中的阶,d= $p n - 1 r$ +1,v∈ $F p n 1 n 2$ 且 $(- v - 1) r$ ≠1	[6]
奇素数p,n=2m,d=2p^m-1,p,m和v的取值见文献[20]	[20]
r)≠1 v∈$\mathbb{F}$\($\mathbb{F}$)^2tk-1	[21]
素数p,n=3m,d=p^2m+p^m+2,p,m和v的取值见文献[3]	[3]
p=2,n=2m,d=s(2^m-1)+1,m,s和v的取值见文献[22]	[22]
v∈$\mathbb{F}$\$\mathbb{F}$且=1	[23-24]
p=3,n=2m,d=3^m+2,v∈ $F 3 n$ \ $F 3 m$ 且 $v 3 m - 1$ =-1	[12,24-25]
p=2,n=rt,r为正整数,t=4,6,10,gcd(t,r)=1,d= $2 n - 1 2 r - 1$ +1,v的取值见文献[11]	[11]
p=2,n=2m,m为奇数且m≥3,d=2^m+1+3,v的取值见文献[10,14]	[10,14]
参数p,n,m,k,t,r以及v的取值范围	参考文献
p=2,n=2m,m为奇数且m≥3,d=2^m-2(2^m+3),v是 $F 2 n$ 上单位圆中的非三次方元	[10]
素数p,n=2m,m,r为正整数,gcd(r-1,p^m+1)=1,gcd(2r-1,p^m+1)=1, d=r(p^m-1)+1,v的取值见文献[26]	[26]
奇素数p,r+1=p,n=rk,d= $p r k - 1 p k - 1$ +1,v∈ $F p n *$ 且 $v p k - 1$ =-1	[12,27]
p=2,n=6k,k为正整数且gcd(k,3)=1,d=2^4k-1+2^2k-1, v∈S且S:={ $ω t (2 2 k - 1)$ \|0≤t≤2^2k+2^4k,3t}	[14,27]
p=2,n=4k,k为正整数,d=(1+2^2k-1)(1+2^2k)+1,v∈ $F 2 2 k *$ 且为 $F 2 2 k$ 中的非三次方元	[14,27]
奇素数p,n=4k,k为正整数,d= $p 4 k - 1 2$ +p^2k,v∈S且S:={ $ω t (p 2 k - 1) + p 2 k - 1 2$ :0≤t≤p^2k}	[14,27]
素数p,n=2m,d=3p^m-2,p,m和v的取值见文献[28]	[28]
素数p,n=2m,d=5p^m-4,p,m和v的取值见文献[29]	[29]
素数p,n=2m,d=7p^m-6,p,m和v的取值见文献[29]	[29]
p=2,n=4k,k为奇数且k≥3,d= $2 n - 1 2 k - 1$ +1,v的取值见文献[30]	[30]
p=3,n=2m,m为奇数,d=2·3^2m-1-3^m-1,v的取值见文献[13]	[13]
p=3,n=2m,m为奇数,d=2·3^m+3,v∈ $F 3 n *$ 且 $T r m 2 m$ (αv)=0或T $r m 2 m$ (α³v)=0	[13]
素数p≡7(mod 12),n=2m,m为奇数,d=2(p^m-1)+1,v的取值见文献[13]	[13]
奇素数p,n+1=p,d=t· $p n - 1 p - 1$ +1(1≤t≤p-2),v∈ $F p n *$ ,且v^p-1=-1	[12]
p=2,n=3m,m≥2,gcd(3,m)=1,d=2^3m-1+2^3m-2-2^2m-2-2^m-2,v∈ $F 2 n *$ 且 $T r m 3 m$ (v^-1)=0	[31]
d=;若m≡3(mod 4) v∈且(ωv^-1)或(ω²v^-1)=0	[31-32]
v是单位圆中的非三次方元	[31]
奇素数p>3,n=2m,m为奇数,6\|p+1,d=p^m+2,v的取值见文献[24,25]	[24-25]
v∈$\mathbb{F}$\$\mathbb{F}$且(v)=0	[24-25]
p=3,d= $3 r - 1 2$ ,r=nk+1,k为偶数,v=1	[33]
p=7,n=6k,k为正整数,d= $7 6 k - 1 6$ +1,v的取值见文献[34]	[34]
p=2,n=2m,m为奇数,d= $(2 m + 1) (2 m - 2) 3$ +1,v∈ $F 2 2 m F 2 m$ 且 $v 3 (2 m - 1)$ =1	[32]
p=3,n=2m,m为正整数,d=(3^m-3^m-1-1)(3^m+1)+1,v∈ $F 3 n *$ 且 $T r m 2 m$ (v)=0	[32]
奇素数p>3,n=2m,gcd(3,p^m-1)=1,s<p^m-1,3s≡1(mod p^m-1), d=(p^m-s-1)(p^m+1)+1,v∈ $F p n *$ ,且v²+ $v 2 p m$ =v¹+p^m	[32]
p=5,n=2m,d=(3·5^m-1-1)(5^m+1)+1,v∈ $F 5 n *$ 且 $T r m 2 m$ (v)=0	[32]
奇素数p≠5,n=2m,gcd(5,pⁿ-1)=1,5s≡1(mod p^m-1),t<p^m-1,t≡-2s(mod p^m-1), d=t(p^m+1)+1,v∈ $F p n *$ ,v²+ $v 2 p m$ =3 $v 1 + p m$	[32]
奇素数p,n=2m,d= $p m + 1 + p m - 2 p 2 p$ (p^m+1)+1或d= $p m - 1 - 1 2$ (p^m+1)+1,v∈ $F p n *$ 且 $T r m 2 m$ (v)=0	[32]
奇素数p,n=2m,d= $p m + p - 2 2$ (p^m+1)+1或d= $p - 1 2$ (p^m+1)+1,v∈ $F p n *$ 且 $T r m 2 m$ (v)=0	[32]
奇素数p,n=2m,m为奇数,p^m≡3(mod 4),gcd(p^2m-1,p^m+2)=1,d=p^m+2,v∈ $F p n *$ 且 $T r m 2 m$ (v)=0	[35]
素数p,n=8k,d= $p 7 k - 1 p k - 1$ +1,p,k,v的取值见文献[36]	[36]
素数p,n=8k,d= $p 8 k - 1 p k - 1$ +1,p,k,v的取值见文献[36]	[36]
参数p,n,m,k,t,r以及v的取值范围	参考文献
任意素数p,n=rt,t,k,r,i为正整数,p^t-1\|r或r=p^k,若p=2,gcd(k,t)≠1, 且i=p^t-p^t-k,d= $i (p n - 1) p t - 1$ +1,v取值见文献[37]	[37]
p=2,n=2m,m为正整数,d= $2 n - 1 3$ +1,v的取值见文献[38]	[38]
p为素数,奇素数t+1≠p,n=rt,gcd(t+1,p^2r-1)=1,d= $p n - 1 p r - 1$ +1,v的取值见文献[39]	[39]
奇素数p,n=rt,t>1,t\|p-1,d= $p (p - 1) r - 1 p r - 1$ +1,v的取值见文献[39]	[39]
奇素数p,n=rt,t>1,t\|p^r-1,d= $p (p r - 1) r - 1 p r - 1$ +1,v的取值见文献[39]	[39]
p=2,n=2m,m为奇数,d= $i (2 n - 1) 3$ +1,其中i∈{1,2},v的取值范围见文献[40]	[40]
素数p,n=2m,d=p^m+2,p,m和v的取值见文献[3,16]	[3,16]
素数p,n=2m,d=2p^m+3,p,m和v的取值见文献[16]	[16]
素数p,n=5k,d= $p n - 1 p k - 1$ +1,p,m和v的取值见文献[41]	[41]

表3

参考文献 41

[1]	DING C. Cyclic Codes from Some Monomials and Trinomials[J]. SIAM Journal on Discrete Mathematics, 2013, 27(4):1977-1994. doi: 10.1137/120882275
[2]	DING C, YUAN J. A Family of Skew Hadamard Difference Sets[J]. Journal of Combinatorial Theory Series A, 2006, 113(7):1526-1535. doi: 10.1016/j.jcta.2005.10.006
[3]	ZIEVE E. Permutation Polynomials Induced from Permutations of Subfields,and Some Complete Sets of Mutually Orthogonal Latin Squares (2013)[J/OL]. [2013-12-04]. https://arxiv.org/abs/1312.1325.
[4]	TUXANIDY A, WANG Q. Compositional Inverses,Complete Mappings,Orthogonal Latin Squares and Bent Functions (2014)[J/OL]. [2014-09-23]. https://arxiv.org/abs/1409.6540.
[5]	MANN H B. The Construction of Orthogonal Latin Squares[J]. Annals of Mathematical Statistics, 1942, 13(4):418-423. doi: 10.1214/aoms/1177731539
[6]	LAIGLE-CHAPUY Y. Permutation Polynomials and Applications to Coding Theory[J]. Finite Fields and Their Applications, 2007, Appl. 13(1):58-70. doi: 10.1016/j.ffa.2005.08.003
[7]	STANICA P, GANGOPADHYAY S, CHATURVEDI A, et al. Investigations on Bent and Negabent Functions via the Nega-Hadamard Transform[J]. IEEE Transactions on Information Theory, 2012, 58(6):4064-4072. doi: 10.1109/TIT.2012.2186785
[8]	ROTHAUS O S. On “Bent” Functions[J]. Journal of Combinatorial Theory,Series A, 1976, 20(3):300-305. doi: 10.1016/0097-3165(76)90024-8
[9]	NIEDERREITER H, ROBINSON K H. Complete Mappings of Finite Fields[J]. Journal of the Australian Mathematical Society, 1982, 33(2):197-212.
[10]	TU Z R, ZENG X Y, HU L. Several Classes of Complete Permutation Polynomials[J]. Finite Fields and Their Applications, 2014, 25:182-193. doi: 10.1016/j.ffa.2013.09.007
[11]	WU G F, LI N, HELLESETH T, et al. Some Classes of Monomial Complete Permutation Polynomials over Finite Fields of Characteristic Two[J]. Finite Fields and Their Applications, 2014, 28:148-165. doi: 10.1016/j.ffa.2014.01.011
[12]	WU G F, LI N, HELLESETH T, et al. Some Classes of Complete Permutation Polynomials over F_q[J]. Science China Mathematics, 2015, 58(10):2081-2094.
[13]	XU G K, CAOX W. Complete Permutation Polynomials over Finite Fields of Odd Characteristic[J]. Finite Fields and Their Applications, 2015, 31:228-240. doi: 10.1016/j.ffa.2014.08.002
[14]	MA J X, ZHANG T, FENG T, et al. Some New Results on Permutation Polynomials over Finite Fields[J]. Designs,Codes and Cryptography, 2017, 83:425-443. doi: 10.1007/s10623-016-0236-1
[15]	TU Z R, ZENG X Y, MAO J X, et al. Several Classes of Complete Permutation Polynomials over Finite Fields of even Characteristic[J]. Finite Fields and Their Applications, 2020, 68:101737. doi: 10.1016/j.ffa.2020.101737
[16]	SHARMA R, GUPTA R. Determination of A Type of Permutation Binomials and Trinomials[J]. Applicable Algebra in Engineering,Communication and Computing, 2020, 31:65-86. doi: 10.1007/s00200-019-00394-y
[17]	许小芳, 曾祥勇, 徐运阁. 完全置换多项式的研究进展[J]. 密码学报, 2019, 6(5):643-664.
	XU Xiaofang, ZENG Xiangyong, XU Yunge. Overview on Complete Permutation Polynomials[J]. Journal of Cryptologic Research, 2019, 6(5):643-664.
[18]	AKBARY A, GHIOCA D, WANG Q. On Constructing Permutations of Finite Fields[J]. Finite Fields and Their Applications, 2011, 17:51-67. doi: 10.1016/j.ffa.2010.10.002
[19]	LIDL R, NIEDERREITER H. Finite Fields[M]. CAMBRIDGE: Cambridge University Press, 1997:1-351.
[20]	HOU X. A Class of Permutation Binomials over Finite Fields[J]. Journal of Number Theory, 2013, 133(10):3549-3558. doi: 10.1016/j.jnt.2013.04.011
[21]	WU B, LIN D. Complete Permutation Polynomials Induced from Complete Permutations of Subfields (2013)[J/OL]. [2013-12-19]. https://arxiv.org/abs/1312.5502.
[22]	TU Z, ZENG X, HU L, et al. A Class of Binomial Permutation Polynomials (2013)[J/OL]. [2013-09-28]. https://arxiv.org/abs/1310.0337.
[23]	SARKAR S, BHATTACHARYA S, ÇEŞMELIOĞLU A. On Some Permutation Binomials of the Form >$x \frac{2^n -1}{k} + 1$ +ax over $F_{2^n}$ :Existence and Count[C]// International Workshop on the Arithmetic of Finite Fields.Heidelberg:Springer, 2012:236-246.
[24]	BASSALYGO L, ZINOVIEV V. On Complete Permutation Polynomials (2014)[J/OL]. [2014-09-13]. http://www.moi.math.bas.bg/acct2014/a9.pdf.
[25]	BASSALYGO L, ZINOVIEV V. Permutation and Complete Permutation Polynomials[J]. Finite Fields and Their Applications, 2015, 33:198-211. doi: 10.1016/j.ffa.2014.11.010
[26]	ZIEVE E. Permutation Polynomials on F_q Induced from Rédei Function Bijections on Subgroups of F_q^*(2013)[J/OL]. [2013-10-07]https://arxiv.org/pdf/1310.0776.pdf.
[27]	MA J, ZHANG T, FENG T, et al. Some New Results on Permutation Polynomials over Finite Fields (2015)[EB/OL]. [2015-06-18]. https://arxiv.org/abs/1506.05525.
[28]	HOU X, LAPPANO S. Determination of a Type of Permutation Binomials over Finite Fields[J]. Journal of Number Theory, 2015, 147:14-23. doi: 10.1016/j.jnt.2014.06.021
[29]	LAPPANO S. A Note Regarding Permutation Binomials over $F_{q^2}$[J]. Finite Fields and Their Applications, 2015, 34:153-160.
[30]	BASSALYGO L, ZINOVIEV V. One Class of Permutation Polynomials over Finite Fields of even Characteristic[J]. Moscow Mathematical Journal, 2015, 15(4):703-713. doi: 10.17323/1609-4514-2015-15-4-703-713
[31]	WU B, LIN D. On Constructing Complete Permutation Polynomials over Finite Fields of even Characteristic[J]. Discrete Applied Mathematics, 2015, 184:213-222. doi: 10.1016/j.dam.2014.11.008
[32]	查正邦, 胡磊. 有限域上置换多项式的几种构造[J]. 密码学报, 2017, 4(3):291-298.
	ZHA Zhengbang, HU Lei. Several Constructions of Permutation Polynomials over Finite Fields[J]. Journal of Cryptologic Research, 2017, 4(3):291-298.
[33]	FERNANDO N. A Note on Permutation Binomials and Trinomials over Finite Fields (2016))[EB/OL]. [2016-09-22]. https://arxiv.org/abs/1609.07162.
[34]	BARTOLI D, GIULIETTI M, ZINI G. On Monomial Complete Permutation Polynomials[J]. Finite Fields and Their Applications, 2016, 41:132-158. doi: 10.1016/j.ffa.2016.06.005
[35]	ZOUBIR N, GUENDA K. Some New Permutation Polynomials over Finite Fields (2017)[EB/OL]. [2017-04-30]. https://arxiv.org/abs/1705.01484.
[36]	BARTOLI D, GIULIETTI M, QUOOS L, et al. Complete Permutation Polynomials from Excepyional Polynomials[J]. Joural of Number Theory, 2017, 176:46-66.
[37]	查正邦, 胡磊. 有限域上几类置换和完全置换[J]. 密码学报, 2019, 6(5):665-674.
	ZHA Zhengbang, HU Lei. A Few Classes of Permutations and Complete Permutations over Finite Fields[J]. Journal of Cryptologic Research, 2019, 6(5):665-674.
[38]	LIU X. Further Results on Some Classes of Permutation Polynomials over Finite Fields (2019)[EB/OL]. [2019-07-08]. https://arxiv.org/abs/1907.03386v1.
[39]	FENG X, LIN D, WANG L, et al. Further Results on Complete Permutation Monomials over Finite Fields[J]. Finite Fields and Their Applications, 2019, 57:47-59. doi: 10.1016/j.ffa.2019.01.003
[40]	LI L S, LI C Y, LI C L, et al. New Classes of Complete Permutation Polynomials[J]. Finite Fields and Their Applications, 2019, 55:177-201. doi: 10.1016/j.ffa.2018.10.001
[41]	ONGAN P, TEMÜR B. A SpecificType of Permutation and Complete Permutation Polynomials over Finite Fields[J]. Journal of Algebra and Its Applications, 2020, 19(4):2050067. doi: 10.1142/S021949882050067X