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

doi:10.19665/j.issn1001-2400.2022.01.010

Abstract

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

CLC Number:

TP309.7

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

Figures/Tables 3

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)

参数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]

References 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

New class of complete permutation monomials over finite fields

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 41

Related Articles 1

Metrics

Comments

Recommended 0

n	d(d^-1)
n=2	1(1)
n=3	1(1)
n=4	1(1),4(4)
n=5	1(1)
n=6	1(1),4(16),8(8),10(19),22(43)
n=7	1(1)
n=8	1(1),4(64),16(16),86(86),154(154)
n=9	1(1),8(64),74(366)
n=10	1(1),4(256),16(64),32(32),34(331),67(397) 94(838),280(559),466(652),683(683),745(931)
n=11	1(1)
n=12	1(1),4(1 024),8(512),16(256),64(64),136(271) 274(3 004),316(946),547(1 093),586(2 341),631(2 836) 1 171(3 511),1366(2 731),1 576( 2 206),1 639(1 639),1 891(3 781) 2 146(2 536),2 276(2 276),2 458(3 277),2 521(2 521),3 151(3 466)