A recent survey of permutation trinomials over finite fields

Varsha Jarali; Prasanna Poojary; G. R. Vadiraja Bhatta; Varsha Jarali; Prasanna Poojary; G. R. Vadiraja Bhatta

doi:10.3934/math.20231495

AIMS Mathematics

2023, Volume 8, Issue 12: 29182-29220. doi: 10.3934/math.20231495

Previous Article Next Article

Research article

A recent survey of permutation trinomials over finite fields

1.
Department of Mathematics, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal, India; varshapjarali@gmail.com
2.
Department of Mathematics, Manipal Institute of Technology Bengaluru, Manipal Academy of Higher Education, Manipal, India; poojary.prasanna@manipal.edu; poojaryprasanna34@gmail.com

Received: 03 July 2023 Revised: 15 September 2023 Accepted: 25 September 2023 Published: 26 October 2023
MSC : 05A05, 11T06

Constructing permutation polynomials is a hot topic in the area of finite fields, and permutation polynomials have many applications in different areas. Recently, several classes of permutation trinomials were constructed. In 2015, Hou surveyed the achievements of permutation polynomials and novel methods. But, very few were known at that time. Recently, many permutation binomials and trinomials have been constructed. Here we survey the significant contribution made to the construction of permutation trinomials over finite fields in recent years. Emphasis is placed on significant results and novel methods. The covered material is split into three aspects: the existence of permutation trinomials of the respective forms $ x^{r}h(x^{s}) $, $ \lambda_{1}x^{a}+\lambda_{2}x^{b}+\lambda_{3}x^{c} $ and $ x+x^{s(q^{m}-1)+1} +x^{t(q^{m}-1)+1} $, with Niho-type exponents $ s, t $.
- permutation polynomial,
- trinomial permutations,
- Niho-type exponents,
- binomial permutations
Citation: Varsha Jarali, Prasanna Poojary, G. R. Vadiraja Bhatta. A recent survey of permutation trinomials over finite fields[J]. AIMS Mathematics, 2023, 8(12): 29182-29220. doi: 10.3934/math.20231495

Related Papers:

Abstract

Constructing permutation polynomials is a hot topic in the area of finite fields, and permutation polynomials have many applications in different areas. Recently, several classes of permutation trinomials were constructed. In 2015, Hou surveyed the achievements of permutation polynomials and novel methods. But, very few were known at that time. Recently, many permutation binomials and trinomials have been constructed. Here we survey the significant contribution made to the construction of permutation trinomials over finite fields in recent years. Emphasis is placed on significant results and novel methods. The covered material is split into three aspects: the existence of permutation trinomials of the respective forms $ x^{r}h(x^{s}) $, $ \lambda_{1}x^{a}+\lambda_{2}x^{b}+\lambda_{3}x^{c} $ and $ x+x^{s(q^{m}-1)+1} +x^{t(q^{m}-1)+1} $, with Niho-type exponents $ s, t $.

References

[1]	A. Akbary, D. Ghoica, Q. Wang, On constructing permutations of finite fields, Finite Fields Appl., 17 (2011), 51–67. https://doi.org/10.1016/j.ffa.2010.10.002 doi: 10.1016/j.ffa.2010.10.002
[2]	T. Bai, Y. Xia, A new class of permutation trinomials constructed from Niho exponents, Cryptography Commun., 10 (2018), 1023–1036. https://doi.org/10.1007/s12095-017-0263-4 doi: 10.1007/s12095-017-0263-4
[3]	D. Bartoli, L. Quoos, Permutation polynomials of the type $x^{r}g(x^{s})$ over $F_{q^2n}$, Design Codes Cryptography, 86 (2018), 1589–1599. https://doi.org/10.1007/s10623-017-0415-8 doi: 10.1007/s10623-017-0415-8
[4]	D. Bartoli, On a conjecture about a class of permutation trinomials, Finite Fields Appl., 52 (2018), 30–50. https://doi.org/10.1016/j.ffa.2018.03.003 doi: 10.1016/j.ffa.2018.03.003
[5]	D. Bartoli, M. Giulietti, Permutation polynomials, fractional polynomials, and algebraic curves, Finite Fields Appl., 51 (2018), 1–16. https://doi.org/10.1016/j.ffa.2018.01.001 doi: 10.1016/j.ffa.2018.01.001
[6]	D. Bartoli, Permutation trinomials over $ F_{q^{3}} $, Finite Fields Appl., 61 (2020), 101597. https://doi.org/10.1016/j.ffa.2019.101597 doi: 10.1016/j.ffa.2019.101597
[7]	D. Bartoli, M. Timpanella, On trinomials of type $ x^{n+m}(1+AX^{m(q-1)}+BX^{n(q-1)}) $, $ n, m $ odd, over $ F_{q^{2}} $, $ q = 2^{2s+1} $, Finite Fields Appl., 72 (2021), 101816. https://doi.org/10.1016/j.ffa.2021.101816 doi: 10.1016/j.ffa.2021.101816
[8]	D. Bartoli, M. Timpanella, A family of permutation trinomials over $F_{q^2}$, Finite Fields Appl., 70 (2021), 101781. https://doi.org/10.1016/j.ffa.2020.101781 doi: 10.1016/j.ffa.2020.101781
[9]	G. R. V. Bhatta, B. R. Shankar, A study of permutation polynomials as Latin squares, Nearrings Nearfields Related Topics, 2017 (2017), 270–281. https://doi.org/10.1142/9789813207363-0025 doi: 10.1142/9789813207363-0025
[10]	S. Bhattacharya, S. Sarkar, On some permutation binomials and trinomials over $F_{2^n}$, Designs Codes Cryptography, 82 (2017), 149–160. https://doi.org/10.1007/s10623-016-0229-0 doi: 10.1007/s10623-016-0229-0
[11]	X. Cao, X. Hou, J. Mi, S. Xu, More permutation polynomials with Niho exponents which permute $ F_{q^{2}} $, Finite Fields Appl., 62 (2020), 101626. https://doi.org/10.1016/j.ffa.2019.101626 doi: 10.1016/j.ffa.2019.101626
[12]	L. Carlitz, Permutations in a finite field, Proc. Amer. Math. Soc., 4 (1953), 538. https://doi.org/10.1090/S0002-9939-1953-0055965-8 doi: 10.1090/S0002-9939-1953-0055965-8
[13]	W. Cherowitzo, $\alpha$-flocks and hyperovals, Geometriae Dedicata, 72 (1998), 221–245. https://doi.org/10.1023/A:1005022808718 doi: 10.1023/A:1005022808718
[14]	H. Deng, D. Zheng, More classes of permutation trinomials with Niho exponents, Cryptography Commun., 11 (2019), 227–236. https://doi.org/10.1007/s12095-018-0284-7 doi: 10.1007/s12095-018-0284-7
[15]	L. Dickson, The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group, Ann. Math., 11 (1896), 65–120. https://doi.org/10.2307/1967217 doi: 10.2307/1967217
[16]	C. Ding, J. Yuan, A family of skew Hadamard difference sets, J. Comb. Theory, 113 (2006), 1526–1535. https://doi.org/10.1016/j.jcta.2005.10.006 doi: 10.1016/j.jcta.2005.10.006
[17]	C. Ding, Cyclic codes from some monomials and trinomials, SIAM J. Discrete Math., 27 (2013), 1977–1994. https://doi.org/10.1137/120882275 doi: 10.1137/120882275
[18]	C. Ding, Z. Zhou, Binary cyclic codes from explicit polynomials over $GF (2m)$, Discrete Math., 321 (2014), 76–89. https://doi.org/10.1016/j.disc.2013.12.020 doi: 10.1016/j.disc.2013.12.020
[19]	C. Ding, L. Qu, Q. Wang, J. Yuan, P. Yuan, Permutation trinomials over finite fields with even characteristic, SIAM J. Discrete Math., 29 (2015), 79–92. https://doi.org/10.1137/140960153 doi: 10.1137/140960153
[20]	Z. Ding, M. Zieve, Determination of a class of permutation quadrinomials, Proc. London Math. Soc., 127 (2023), 221–260. https://doi.org/10.1112/plms.12540 doi: 10.1112/plms.12540
[21]	H. Dobbertin, Uniformly representable permutation polynomials, Springer, 2022.
[22]	N. Fernando, X. Hou, S. Lappano, A new approach to permutation polynomials over finite fields, Ⅱ, Finite Fields Appl., 22 (2013), 122–158. https://doi.org/10.1016/j.ffa.2013.01.001 doi: 10.1016/j.ffa.2013.01.001
[23]	N. Fernando, A note on permutation binomials and trinomials over finite fields, arXiv, 2016. https://doi.org/10.48550/arXiv.1609.07162
[24]	W. Fulton, Algebraic curves, University of Michigan, 1989.
[25]	H. Guo, S. Wang, H. Song, X. Zhang, J. Liu, A new method of construction of permutation trinomials with coefficients 1, arXiv, 2021. https://doi.org/10.48550/arXiv.2112.14547
[26]	R. Gupta, R. Sharma, Some new classes of permutation trinomials over finite fields with even characteristic, Finite Fields Appl., 41 (2016), 89–96. https://doi.org/10.1016/j.ffa.2016.05.004 doi: 10.1016/j.ffa.2016.05.004
[27]	C. Hermite, Sur les fonctions de sept lettres, Académie Sciences, 1863.
[28]	X. Hou, A class of permutation binomials over finite fields, J. Number Theory, 133 (2013), 3549–3558. https://doi.org/10.1016/j.jnt.2013.04.011 doi: 10.1016/j.jnt.2013.04.011
[29]	X. Hou, A class of permutation trinomials over finite fields, arXiv, 2013. https://doi.org/10.48550/arXiv.1303.0568
[30]	X. Hou, Determination of a type of permutation trinomials over finite fields, Acta Arith., 3 (2014), 253–278. https://doi.org/10.4064/aa166-3-3 doi: 10.4064/aa166-3-3
[31]	X. Hou, Determination of a type of permutation trinomials over finite fields, $ II $, Finite Fields Appl., 35 (2015), 16–35. https://doi.org/10.1016/j.ffa.2015.03.002 doi: 10.1016/j.ffa.2015.03.002
[32]	X. Hou, A survey of permutation binomials and trinomials over finite fields, Contemp. Math., 632 (2015), 177–191. https://doi.org/10.1090/conm/632/12628 doi: 10.1090/conm/632/12628
[33]	X. Hou, Z. Tu, X. Zeng, Determination of a class of permutation trinomials in characteristic three, Finite Fields Appl., 61 (2020), 101596. https://doi.org/10.1016/j.ffa.2019.101596 doi: 10.1016/j.ffa.2019.101596
[34]	X. Hou, On the Tu-Zeng permutation trinomial of type $ (1/ 4, 3/ 4) $, Discrete Math., 344 (2021), 112241. https://doi.org/10.1016/j.disc.2020.112241 doi: 10.1016/j.disc.2020.112241
[35]	V. Jarali, P. Poojary, G. R. V. Bhatta, Construction of permutation polynomials using additive and multiplicative characters, Symmetry, 14 (2022), 1539. https://doi.org/10.3390/sym14081539 doi: 10.3390/sym14081539
[36]	G. Khachatrian, M. Kyureghyan, Permutation polynomials and a new public-key encryption, Discrete Appl. Math., 216 (2017), 622–626. https://doi.org/10.1016/j.dam.2015.09.001 doi: 10.1016/j.dam.2015.09.001
[37]	G. Kyureghyan, M. Zieve, Permutation polynomials of the form $x+ \gamma Tr (x^{k})$, arXiv, 2016. https://doi.org/10.48550/arXiv.1603.01175
[38]	J. Lee, Y. Park, Some permuting trinomials over finite fields, Acta Math. Sci., 17 (1997), 250–254. https://doi.org/10.1016/S0252-9602(17)30842-1 doi: 10.1016/S0252-9602(17)30842-1
[39]	K. Li, L. Qu, C. Li, S. Fu, New permutation trinomials constructed from fractional polynomials, Acta Arith., 183 (2018), 101–116. https://doi.org/10.4064/aa8461-11-2017 doi: 10.4064/aa8461-11-2017
[40]	K. Li, L. Qu, X. Chen, New classes of permutation binomials and permutation trinomials over finite fields, Finite Fields Appl., 43 (2017), 69–85. https://doi.org/10.1016/j.ffa.2016.09.002 doi: 10.1016/j.ffa.2016.09.002
[41]	N. Li, On two conjectures about permutation trinomials over $ F_{3^2k} $, Finite Fields Appl., 47 (2017), 1–10. https://doi.org/10.1016/j.ffa.2017.05.003 doi: 10.1016/j.ffa.2017.05.003
[42]	N. Li, T. Helleseth, Several classes of permutation trinomials from Niho exponents, Cryptography Commun., 9 (2017), 693–705. https://doi.org/10.1007/s12095-016-0210-9 doi: 10.1007/s12095-016-0210-9
[43]	K. Li, L. Qu, X. Chen, C. Li, Permutation polynomials of the form $cx+ Tr_{q^{l}/q}(x^{a}) $ and permutation trinomials over finite fields with even characteristic, Cryptography Commun., 10 (2018), 531–554. https://doi.org/10.1007/s12095-017-0236-7 doi: 10.1007/s12095-017-0236-7
[44]	L. Li, C. Li, C. Li, X. Zeng, New classes of complete permutation polynomials, Finite Fields Appl., 55 (2019), 177–201. https://doi.org/10.1016/j.ffa.2018.10.001 doi: 10.1016/j.ffa.2018.10.001
[45]	N. Li, T. Helleseth, New permutation trinomials from Niho exponents over finite fields with even characteristic, Cryptography Commun., 11 (2019), 129–136. https://doi.org/10.1007/s12095-018-0321-6 doi: 10.1007/s12095-018-0321-6
[46]	N. Li, X. Zeng, A survey on the applications of Niho exponents, Cryptography Commun., 11 (2019), 509–548. https://doi.org/10.1007/s12095-018-0305-6 doi: 10.1007/s12095-018-0305-6
[47]	R. Lidl, H. Niederreiter, Finite fields, Cambridge University Press, 1997. https://doi.org/10.1017/CBO9781139172769
[48]	X. Liu, Further results on some classes of permutation polynomials over finite fields, arXiv, 2019. https://doi.org/10.48550/arXiv.1907.03386
[49]	Q. Liu, Y. Sun, Several classes of permutation trinomials from Niho exponents over finite fields of characteristic 3, J. Algebra Appl., 18 (2019), 1950069. https://doi.org/10.1142/S0219498819500695 doi: 10.1142/S0219498819500695
[50]	Q. Liu, X. Liu, J. Zou, A class of new permutation polynomials over $ F_{2^{n}} $, J. Math., 2021 (2021), 5872429. https://doi.org/10.1155/2021/5872429 doi: 10.1155/2021/5872429
[51]	Q. Liu, Two classes of permutation polynomials with niho exponents over finite fields with even characteristic, Turk. J. Math., 46 (2022), 919–928. https://doi.org/10.55730/1300-0098.3132 doi: 10.55730/1300-0098.3132
[52]	J. Ma, T. Zhang, T. Feng, G. Ge, Some new results on permutation polynomials over finite fields, Designs Codes Cryptography, 83 (2017), 425–443. https://doi.org/10.1007/s10623-016-0236-1 doi: 10.1007/s10623-016-0236-1
[53]	J. Ma, G. Ge, A note on permutation polynomials over finite fields, Finite Fields Appl., 48 (2017), 261–270. https://doi.org/10.1016/j.ffa.2017.08.003 doi: 10.1016/j.ffa.2017.08.003
[54]	Y. Niho, Multi-valued cross-correlation functions between two maximal linear recursive sequences, University of Southern California, 1972.
[55]	T. Niu, K. Li, L. Qu, Q. Wang, Finding compositional inverses of permutations from the AGW criterion, IEEE Trans. Inf. Theory, 67 (2021), 4975–4985. https://doi.org/10.1109/TIT.2021.3089145 doi: 10.1109/TIT.2021.3089145
[56]	J. Peng, L. Zheng, C. Wu, H. Kan, Permutation polynomials $ x^{2^{k+1}+3}+ax^{2^{k}+2}+bx $ over $ F_{2^2k} $ and their differential uniformity, Sci. China Inf. Sci., 63 (2020), 209101. https://doi.org/10.1007/s11432-018-9741-6 doi: 10.1007/s11432-018-9741-6
[57]	H. Peter, G. Korchmáros, F. Torres, F. Orihuela, Algebraic curves over a finite field, Princeton University Press, 2008.
[58]	X. Qin, L. Yan, Constructing permutation trinomials via monomials on the subsets of $\mu_{q+1}$, Appl. Algebra Eng. Commun. Comput., 34 (2023), 321–334. https://doi.org/10.1007/s00200-021-00505-8 doi: 10.1007/s00200-021-00505-8
[59]	R. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21 (1978), 120–126. https://doi.org/10.1145/359340.359342 doi: 10.1145/359340.359342
[60]	R. K. Sharma, R. Gupta, Determination of a type of permutation binomials and trinomials, Appl. Algebra Eng. Commun. Comput., 31 (2020), 65–86. https://doi.org/10.1007/s00200-019-00394-y doi: 10.1007/s00200-019-00394-y
[61]	R. Singh, K. Sarma, A. Saikia, Poly-dragon: an efficient multivariate public key cryptosystem, J. Math. Cryptology, 4 (2011), 349–364. https://doi.org/10.1515/jmc.2011.002 doi: 10.1515/jmc.2011.002
[62]	R. Singh, K. Sarma, A. Saikia, A public key cryptosystem using a group of permutation polynomials, Tatra Mt. Math. Publ., 77 (2020), 139–162. http://doi.org/10.2478/tmmp-2020-0013 doi: 10.2478/tmmp-2020-0013
[63]	H. Stichtenoth, Algebraic function fields and codes, Springer Science & Business Media, 2009. http://doi.org/10.1007/978-3-540-76878-4
[64]	Z. Tu, X. Zeng, L. Hu, C. Li, A class of binomial permutation polynomials, arXiv, 2013. https://doi.org/10.48550/arXiv.1310.0337
[65]	Z. Tu, X. Zeng, L. Hu, Several classes of complete permutation polynomials, Finite Fields Appl., 25 (2014), 182–193. https://doi.org/10.1016/j.ffa.2013.09.007 doi: 10.1016/j.ffa.2013.09.007
[66]	Z. Tu, X. Zeng, C. Li, T. Helleseth, A class of new permutation trinomials, Finite Fields Appl., 50 (2018), 178–195. https://doi.org/10.1016/j.ffa.2017.11.009 doi: 10.1016/j.ffa.2017.11.009
[67]	Z. Tu, X. Zeng, Two classes of permutation trinomials with Niho exponents, Finite Fields Appl., 53 (2018), 99–112. https://doi.org/10.1016/j.ffa.2018.05.007 doi: 10.1016/j.ffa.2018.05.007
[68]	Z. Tu, X. Zeng, A class of permutation trinomials over finite fields of odd characteristic, Cryptography Commun., 11 (2019), 563–583. https://doi.org/10.1007/s12095-018-0307-4 doi: 10.1007/s12095-018-0307-4
[69]	D. Wan, R. Lidl, Permutation polynomials of the form $x^rf(x^{\frac{(q-1)}{d}})$ and their group structure, Monatsh. Math., 112 (1991), 149–163. https://doi.org/10.1007/BF01525801 doi: 10.1007/BF01525801
[70]	Q. Wang, Cyclotomic mapping permutation polynomials over finite fields, Springer, 2007.
[71]	Y. Wang, Z. Zha, W. Zhang, Six new classes of permutation trinomials over $ F_{3^3k}$, Appl. Algebra Eng. Commun. Comput., 29 (2018), 479–499. https://doi.org/10.1007/s00200-018-0353-3 doi: 10.1007/s00200-018-0353-3
[72]	Y. Wang, W. Zhang, Z. Zha, Six new classes of permutation trinomials over $ F_{2^{n}}^{} $, SIAM J. Discrete Math.*, 32 (2018), 1946–1961. https://doi.org/10.1137/17M1156666 doi: 10.1137/17M1156666
[73]	B. Wu, D. Lin, On constructing complete permutation polynomials over finite fields of even characteristic, Discrete Appl. Math., 184 (2015), 213–222. https://doi.org/10.1016/j.dam.2014.11.008 doi: 10.1016/j.dam.2014.11.008
[74]	D. Wu, P. Yuan, C. Ding, Y. Ma, Permutation trinomials over $ F_{2^{m}} $, Finite Fields Appl., 46 (2017), 38–56. https://doi.org/10.1016/j.ffa.2017.03.002 doi: 10.1016/j.ffa.2017.03.002
[75]	G. Wu, N. Li, Several classes of permutation trinomials over $F_{5^{n}}$ from Niho exponents, Cryptography Commun., 11 (2019), 313–324. https://doi.org/10.1007/s12095-018-0291-8 doi: 10.1007/s12095-018-0291-8
[76]	X. Xie, N. Li, L. Xu, X. Zeng, X. Tang, Two new classes of permutation trinomials over $F_{q^{3}}$ with odd characteristic, Discrete Math., 346 (2023), 113607. https://doi.org/10.1016/j.disc.2023.113607 doi: 10.1016/j.disc.2023.113607
[77]	P. Yaun, Compositional inverses of AGW-PPs-dedicated to professor cunsheng ding for his 60th birthday, Adv. Math. Commun., 16 (2022), 1185–1195. https://doi.org/10.3934/amc.2022045 doi: 10.3934/amc.2022045
[78]	P. Yaun, Permutation polynomials and their compositional inverses, arXiv, 2022, https://doi.org/10.48550/arXiv.2206.04252
[79]	P. Yuan, Local method for compositional inverses of permutational polynomials, arXiv, 2022. https://doi.org/10.48550/arXiv.2211.10083
[80]	Z. Zha, L. Hu, S. Fan, Further results on permutation trinomials over finite fields with even characteristic, Finite Fields Appl., 45 (2017), 43–52. https://doi.org/10.1016/j.ffa.2016.11.011 doi: 10.1016/j.ffa.2016.11.011
[81]	D. Zheng, M. Yuan, L. Yu, Two types of permutation polynomials with special forms, Finite Fields Appl., 56 (2019), 1–16. https://doi.org/10.1016/j.ffa.2018.10.008 doi: 10.1016/j.ffa.2018.10.008
[82]	L. Zheng, H. Kan, J. Peng, Two classes of permutation trinomials with Niho exponents over finite fields with even characteristic, Finite Fields Appl., 68 (2020), 101754. https://doi.org/10.1016/j.ffa.2020.101754 doi: 10.1016/j.ffa.2020.101754
[83]	L. Zheng, H. Kan, J. Peng, D. Tang, Two classes of permutation trinomials with Niho exponents, Finite Fields Appl., 70 (2021), 101790. https://doi.org/10.1016/j.ffa.2020.101790 doi: 10.1016/j.ffa.2020.101790
[84]	L. Zheng, B. Liu, H. Kan, J. Peng, D. Tang, More classes of permutation quadrinomials from niho exponents in characteristic two, Finite Fields Appl., 78 (2022), 101962. https://doi.org/10.1016/j.ffa.2021.101962 doi: 10.1016/j.ffa.2021.101962
[85]	M. Zieve, On some permutation polynomials over of the form $x^{r}h(x^{\frac{q-1}{d}})$, Proc. Amer. Math. Soc., 137 (2009), 2209–2216.
[86]	M. Zieve, Permutation polynomials on $F_q$ induced form R´edei function bijections on subgroups of $F_q^$, arXiv*, 2013. https://doi.org/10.48550/arXiv.1310.0776
[87]	M. Zieve, A note on the paper arXiv: 2112.14547, arXiv, 2022. https://doi.org/10.48550/arXiv.2201.01106

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)