Open access peer-reviewed chapter - ONLINE FIRST

Some Proposed Problems on Permutation Polynomials over Finite Fields

By Mritunjay Kumar Singh and Rajesh P. Singh

Submitted: April 26th 2021Reviewed: July 9th 2021Published: August 9th 2021

DOI: 10.5772/intechopen.99351

Downloaded: 61

Abstract

From the 19th century, the theory of permutation polynomial over finite fields, that are arose in the work of Hermite and Dickson, has drawn general attention. Permutation polynomials over finite fields are an active area of research due to their rising applications in mathematics and engineering. The last three decades has seen rapid progress on the research on permutation polynomials due to their diverse applications in cryptography, coding theory, finite geometry, combinatorics and many more areas of mathematics and engineering. For this reason, the study of permutation polynomials is important nowadays. In this chapter, we propose some new problems in connection to permutation polynomials over finite fields by the help of prime numbers.

Keywords

  • finite field
  • permutation polynomial

1. Introduction to permutation polynomials

In this section, we collect some basic facts about permutation polynomials over a finite field that will be frequently used throught the chapter. First it will be convenient to define permutation polynomial over a finite field.

Definition 1.A polynomial fxFqxis said to be a permutation polynomial over Fqfor which the associated polynomial function cfcia a permutation of Fq, that is, the mapping from Fqto Fqdefined by fis one–one and onto.

Finite fields are polynomially complete, that is, every mapping from Fqinto Fqcan be represented by a unique polynomial over Fq. Given any arbitrary function ϕ:FqFq, the unique polynomial gFqxwith degg<qrepresenting ϕcan be found by the formula gx=cFqϕc1xcq1, see ([1], Chapter 7).

Two polynomials represent the same function if and only if they are the same by reduction modulo xqx, according to the following result.

Lemma 1.[1] Forf,gFqxwe havefα=gαfor allαFqif and only iffxgxmodxqx.

Due to the finiteness of the field, the followings are the equivalent conditions for a polynomial to be a permutation polynomial.

Definition 2.The polynomial fFqxis a permutation polynomial of Fqif and only if one of the following conditions holds:

  1. the function f:cfcis onto;

  2. the function f:cfcis one-to-one;

  3. fx=ahas a solution in Fqfor each aFq;

  4. fx=ahas a unique solution in Fqfor each aFq.

1.1 Criteria for permutation polynomials

Some well-known criteria for being permutation polynomials are the following.

1.1.1 First criterion for permutation polynomials

The first and in some way most useful, criterion was proved by Hermite for qprime and by Dickson for general q. This criterion has special name what is called Hermite’s criterion.

Theorem 3(Hermite’s criterion). [1] A polynomialfxFqxis a permutation polynomial ofFqif and only if following two conditions hold:

  1. fxhas exactly one root inFq;

  2. for each integertwith1tq2and t not divisible byp, the residuefxtmodxqxhas degreeq2.

For the detailed proof, one can see [1]. Above theorem is mainly used to show negative result. The following is a useful corollary for this purpose.

Corollary 4.There is no permutation polynomial of degreeddividingq1overFq.

Proof. We note that degfq1d=q1. The proof follows from the last condition of Hermite’s criterion.

Remark 5.Hermite’s criterion is interesting theoretically but difficult to use in practice.

1.1.2 Second criterion for permutation polynomials

Theorem 6.[1] LetfFqx. Write

Df=fbfaba:abFq.

Thenfxis a permutation polynomial ofFqif and only if0Df.

1.1.3 Third criterion for permutation polynomials

Theorem 7.[1] The polynomialfFqxis a permutation polynomial ofFqif and only if

cFqχfc=0

for all nontrivial additive charactersχofFq.

1.1.4 Fourth criterion for permutation polynomials

Theorem 8.[1] Let the trace mapTr:FqnFqbe defined asTrx=x+xq++xqn1. Then the polynomialfFqxis a permutation polynomial ofFqif and only if for every nonzeroηFq,

xFqζTrηfx=0,

whereζ=e2πipis a primitivep-th root of unity.

In what follows, we will discuss some well known classes of permutation polynomials which are commonly used.

1.2 Some well-known classes of permutation polynomials

In this subsection, several basic results on permutation polynomials are presented. Many times, we see that one of these general classes are obtained by simplifying complicated classes of permutation polynomials for proving their permutation nature.

Theorem 9.[1] Every linear polynomial, that is, polynomial of the formax+b,a0over finite field is a permutation polynomial.

Theorem 10.[1] The monomialxnis a permutation polynomial overFqif and only ifgcdnq1=1.

Theorem 11.Letgxandhxbe two polynomials overFq. Thenfx=ghxis a permutation polynomial overFqif and only if bothgxandhxpermuteFq.

1.3 Open problems on permutation polynomials

Very little is known concerning which polynomials are permutation polynomials, despite the attention of numerous authors. There are so many open problems and conjectures on permutation polynomials over finite fields but here we are listing few of them.

Open Problem 12.[2] Find new classes of permutation polynomials of Fq.

Although several classes of permutation polynomials have been found in recent years, but, an explicit and unified characterization of permutation polynomials is not known and seems to be elusive today. Therefore, it is both interesting and important to find more explicit classes of permutation polynomials.

Open Problem 13.[2] Find inverse polynomial of known classes of permutation polynomials over Fq.

The construction of permutation polynomials over finite fields is an old and difficult problem that continues to attract interest due to their applications in various area of mathematics. However, the problem of determining the compositional inverse of known classes of permutation polynomial seems to be an even more complicated problem. In fact, there are very few known permutation polynomials whose explicit compositional inverses have been obtained, and the resulting expressions are usually of a complicated nature except for the classes of the permutation linear polynomials, monomials, Dickson polynomials.

Open Problem 14.[2] Find Nd, where Nd=Ndqdenote the number of permutation polynomials of degree dover Fq.

To date, there is no method for counting the exact number of permutation polynomials of given degree. However, Koyagin and Pappalardi [3, 4], found the asymptotic formula for the number of permutations for which the associated permutation polynomial has degree smaller than q2.

1.4 Applications of permutation polynomials

The study of permutation polynomials would not complete without mentioning their applications in other area of mathematics and engineering. It is a major subject in the theory and applications of finite fields. The study of permutation polynomials over the finite fields is essentially about relations between the algebraic and combinatoric structures of finite fields. Nontrivial permutation polynomials are usually the results of the intricate and sometimes mysterious interplay between the two structures. Here we mention some applications of permutation polynomials.

1.5 Coding theory

In coding theory, error correcting codes are fundamental to many digital communication and storage systems, to improve the error performance over noisy channels. First proposed in the seminal work of Claude Shannon [5], they are now ubiquitous and included even in consumer electronic systems such as compact disc players and many others. Permutation polynomials have been used to construct error correcting codes. Laigle-Chapuy [6] proposed a conjecture equivalent to a conjecture related to cross-correlation functions in coding theory. In [7], Chunlei and Helleseth derived several classes of p-ary quasi-perfect codes using permutation polynomials over finite fields. In 2005, Carlet, Ding and Yuan [8] obtained Linear codes using planar polynomials over finite fields.

1.6 Cryptography

The advent of public key cryptography in the 1970’s has generated innumerable security protocols which find widespread application in securing digital communications, electronic funds transfer, email, internet transactions and the like. In recent years, permutation polynomials over finite fields has been used to design public key cryptosystem. Singh, Saikia and Sarma [9, 10, 11, 12, 13, 14, 15] designed efficient multivariate public key cryptosystem using permutation polynomials over finite fields. The same authors used a group of linearized permutation polynomials to design an efficient multivariate public key cryptosystem [16].

Permutation polynomials with low differential uniformity are important candidate functions to design substitution boxes (S-boxes) of block ciphers. S-boxes can be constructed from permutation polynomials over even characteristics [17] with desired cryptographic properties such as low differential uniformity and play important role in iterated block ciphers.

1.7 Finite geometry

Permutation polynomial fxFqxis called a complete permutation polynomial if fx+xis also a permutation polynomial and an orthomorphism polynomial if fxxis also a permutation polynomial. Orthomorphism polynomials can be used in check digit systems to detect single errors and adjacent transpositions whereas complete permutation polynomials to detect single and twin errors. For more details on complete mappings and orthomorphisms over finite fields, we refer to the reader [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]. In addition, complete permutation polynomials are very useful in the study of orthogonal latin squares and orthomorphism polynomials are useful in close connection to hyperovals in finite projective plane. In 1968, planar functions were introduced by Dembowski and Ostrom [20] in context of finite geometry to describe projective planes with specific properties. Since 1991, planar functions have attracted interest also from cryptography as functions with optimal resistance to differential cryptanalysis.

Advertisement

2. Some proposed problems

Let Fqdenotes finite fields with q=2melements. Nowaday permutation polynomials are an interesting subject for study not for only research purposes but also for their various applications in many areas of mathematics and engineering. We refer [21] to the reader for recent advances and contributions to the area.

The rising applications of permutation polynomials in mathematics and engineering from last decade propels us to do new research. Recently, permutation polynomials with few terms over finite fields paying more attention due to their simple algebraic form and some extraordinary properties. We refer to the reader [22, 23, 24, 25] for some recent developments. This motivates us to propose some new problems. In this chapter, by the help of prime numbers, we constructed several new polynomials that have no root in μ2m+1and two of them are generalizations of known ones. The constructed polynomials here may lay a good foundation for finding new classes of permutation polynomials.

Throughout the chapter, for a positive integer d, the set of d-th roots of unity in the algebraic closure F¯qof Fqis denoted by μd. That is,

μd=xF¯q:xd=1.

For every element xFq, we denote x2mby x¯in analogous to the usual complex conjugation. Clearly, xx¯,x+x¯Fq. Define the unit circle of Fqas

μ2m+1=xFq:x2m+1=xx¯=1.

The permutation polynomial of the form xrhxq1dare interesting and have been paid attention, where hxFqxwith ddividing q1and 1rq1d. The permutation behavior of this type of polynomials are investigated by Park and Lee [26] and Zieve [27].

Lemma 2([26, 27]). Letr,d>0withddividingq1andhxFqx. Thenfx=xrhxq1dpermutesFqif and only if

  1. gcdrq1d=1and

  2. xrhxq1dpermutesμd.

In view of Lemma 2, the permutation property of xrhxq1dis decided by whether xrhxq1dpermutes μd. In the process to prove that xrhxq1dpermutes μd, first we need to prove that hxhas no root in μd[22]. Thus the polynomials which have no roots in μdare interesting and can be used to construct new classes of permutation polynomials. Therefore, it is is both interesting and important to find more polynomials that have no roots in μdwhich play key role in showing the permutation property of xrhxq1d. For more recent progresses about this type of constructions, we refer [23, 25]. In next section, we also need the following definition.

Definition 15.Two polynomials are said to be conjugate to each other if one is obtained by raising 2m-th power and multiplying them by the highest degree term of the other.

Next, we propose some new problems by reviewing various recent contributions. The polynomials that have no roots in μ2m+1play important role in theory of finite fields because these polynomials may give rise to a new class of permutation polynomials.

Let p122m1, and let the binary representation of pbe

p=k=0m1pk2k

with pk01. Define the weight of pby

wp=k=0m1pk.

We define a polynomial function over F2mas

Lpx=k=0m1pkx2k.

For example,

L11x=1+x+x3
L13x=1+x2+x3
L19x=1+x+x4.

We observe that there is a good connection between prime numbers and polynomials that have no roots in μ2m+1in the sense that most of these polynomials can be derived from prime numbers. In this way, for the prime numbers 11, 13 and 19 we get the polynomials L11x,L13xand L19xrespectively that have no roots in μ2m+1. This result is obtained by Gupta and Sharma in [22]. More precisely,

Lemma 3([22]). Letm>0be integer. Then each of the polynomials1+x+x3,1+x2+x3and1+x+x4have no roots inμ2m+1.

Similarly, for the primes 59 and 109, we obtain the same polynomials as in [25] of Xu Guangkui et al.

Lemma 4([25]). Letm>0be integer. Then each of the polynomials1+x+x3+x4+x5and1+x2+x3+x5+x6have no roots inμ2m+1.

It is not necessary that all polynomials are obtained from prime numbers. For example, the polynomials 1+x3+x4by Gupta and Sharma in [22] and 1+x+x2+x4+x5by Xu Guangkui et al. [25] are obtained corresponding to the number 25 and 55 respectively. In this respect, we propose the following problem.

Problem 16.Which prime numbers will give polynomials that have no roots inμ2m+1?.

The generalization of Lemma 2.2 of [22] corresponding to the polynomials 1+x+x3and 1+x2+x3are given by the following lemma.

Lemma 5.For sufficiently large positive integersmandn, each of the polynomials1+xn+x2n1and1+xn+x2n+1have no roots inμ2m+1.

Proof. Suppose αμ2m+1satisfies the equation

1+αn+α2n1=0.E1

Raising both sides of (1) to the 2m-th power and multiplying by α2n1, we get

1+αn1+α2n1=0.E2

Adding (1) and (2), we get

αn1+αn=0

Since α0, which gives α=1. But α=1does not satisfy (1), a contradiction. Hence 1+xn+x2n1has no roots in μ2m+1. Similarly, we can show that the polynomial 1+xn+x2n+1has no roots in μ2m+1.

In particular, we get the following lemma by Gupta and Sharma [22].

Lemma 6([22]). Letm>0be integer. Then each of the polynomials1+x+x3and1+x2+x3have no roots inμ2m+1.

Based on the Lemma 5, we propose the following problem.

Problem 17.Leth1x=1+xn+x2n1andh2x=1+xn+x2n+1. Characterizenandrsuch that the polynomialsxrh1x2m1andxrh2x2m1permutesμ2m+1.

By the help of prime numbers below 1000, we obtain the following polynomials that have no roots in μ2m+1. Most of these polynomials are directly or indirectly associated with prime numbers in the sense that corresponding to either each polynomial or their conjugate polynomial, a prime number can be obtained. The proof of the following lemmas can be done in similar fashion as in [22].

Lemma 7.For a positive integerm, each of the polynomials1+x+x2+x7+x8, 1+x+x6+x7+x8, 1+x+x3+x7+x8, 1+x+x5+x7+x8, 1+x+x4+x8+x9, 1+x+x5+x8+x9, 1+x2+x3+x5+x8, 1+x3+x5+x6+x8, 1+x+x3+x4+x8, 1+x4+x5+x7+x8, 1+x2+x3+x6+x8, 1+x2+x5+x6+x8, 1+x3+x4+x7+x8, 1+x+x4+x5+x8, 1+x3+x4+x6+x9, 1+x3+x5+x6+x9, 1+x+x2+x7+x9, 1+x2+x7+x8+x9, 1+x2+x4+x7+x9, 1+x2+x5+x7+x9have no roots inμ2m+1.

Lemma 8.For a positive integerm, each of the polynomials1+x+x3+x5+x6+x7+x8, 1+x+x2+x3+x5+x7+x8, 1+x+x2+x3+x6+x7+x8, 1+x+x2+x5+x6+x7+x8, 1+x+x4+x5+x6+x7+x8, 1+x+x2+x3+x4+x7+x8, 1+x+x3+x5+x6+x8+x9, 1+x+x3+x4+x6+x8+x9, 1+x+x3+x4+x5+x8+x9, 1+x+x4+x5+x6+x8+x9, 1+x+x2+x3+x7+x8+x9, 1+x+x2+x6+x7+x8+x9, 1+x+x2+x4+x7+x8+x9, 1+x+x2+x5+x7+x8+x9, 1+x2+x3+x4+x6+x7+x9, 1+x2+x3+x5+x6+x7+x9, 1+x2+x3+x4+x5+x7+x9, 1+x2+x4+x5+x6+x7+x9, have no roots inμ2m+1.

Lemma 9.For a positive integerm, each of the polynomials1+x+x2+x3+x4+x6+x7+x8+x9, 1+x+x2+x3+x5+x6+x7+x8+x9have no roots inμ2m+1.

The above list of polynomials are not complete. However, computational experiments shows that there should be more polynomials. A complete determination of all polynomials with few terms over finite fields seems to be out of reach for the time bing.

Now, we are in condition to propose the following problem in connection to above three lemmas.

Problem 18.Find new classes of permutation polynomials corresponding to polynomials obtained in Lemmas 7, 8 and 9.

Advertisement

Classification

AMS 2020 MSC: 11T06.

DOWNLOAD FOR FREE

chapter PDF

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Mritunjay Kumar Singh and Rajesh P. Singh (August 9th 2021). Some Proposed Problems on Permutation Polynomials over Finite Fields [Online First], IntechOpen, DOI: 10.5772/intechopen.99351. Available from:

chapter statistics

61total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us