Christian A. Rodríguez
Alex D. Santos
Computer Science Department
College of Natural Science
(*Para poder ver las formulas que se encuentran en este artículo debe utilizar un motor de búsqueda que no sea Google Chrome)
Permutation polynomials over finite fields have many applications in areas such as coding theory and cryptography. We consider polynomials of the form , where and . We construct partitions of these polynomials where polynomials in the same partition have value sets of equal cardinality. As a consequence we provide families of permutation polynomials.
Los polinomios de permutación definidos sobre cuerpos finitos tienen muchas aplicaciones en campos como la teoría de códigos y la criptografía. Consideramos polinomios de la forma , donde y . Construimos particiones de estos polinomios en las que los polinomios en la misma partición tienen conjuntos de valores con la misma cardinalidad. Como consecuencia proveemos familias de polinomios de permutación.
Many people have studied permutation polynomials over finite fields because of their applications in cryptography and coding theory. Moreover, permutation polynomials provide an efficient way of generating permutations when working with a limited amount of storage.
An example of applications of permutation polynomials over finite fields are RSA-type cryptosystems. In some of these systems secret messages are encoded as elements of a field with a sufficiently large . The encryption operator used for these systems is a permutation of the field and needs to be efficiently computable. Expressing this operator in terms of a permutation polynomial is simple and efficient.
Permutation polynomials are a very broad field of study and researchers have studied them by cases (Lidl & Mullen, 2013). It is known that a polynomial of the form is a permutation polynomial over if and only if (Panario & Mullen, 2013). Binomials that produce permutation polynomials have been studied extensively. The next logical case to be studied are trinomials.
We have found that within the family of polynomials of the form
where and , there are many permutation polynomials. Given a pair of coefficients such that is a permutation polynomial, we provide a construction to obtain other permutation polynomials.
We begin by introducing some background concepts.
Defenition 2.1. A permutation of a set is an ordering of the elements of .
Example 2.2. Consider . Then and are permutations of the set .
A function gives a permutation of if and only if is one to one and onto.
Defenition 2.3. Let be a function defined over a set . The value set of is defined as .
Example 2.4. Consider , . Then .
We are interested in functions where and is a finite field.
Defenition 2.5. A finite field is a field with elements, where is a prime.
Example 2.6. Let . Then with the operations of addition and multiplication modulo is a field. In general, for prime.
Since is finite, we have that a polynomial is a permutation polynomial of if it gives a one to one function . Also, a polynomial is a permutation polynomial of if and only if .
Example 2.7. Consider the polynomial defined over . We have that and . Therefore is a permutation polynomial over .
An important property of finite fields, used throughout our results, is the existence of a primitive root. This is an element of the field that generates all the elements in the field, except .
Defenition 2.8. A primitive root is a generator of the multiplicative group .
Example 2.9. Consider the finite field . We have that . Therefore is a primitive root of .
Example 2.10. Consider the finite field . We have that . Therefore is not a primitive root of .
Primitive roots are useful in many topics because of the properties they have. We are interested in the following property that relates powers of a primitive root. This property is fundamental in order to prove many of our results.
Proposition 2.11. Let be a primitive root of . Then if and only if .
3Families of Polynomials with Value Sets of the Same Cardinality
We consider polynomials of the form over . Given and these polynomials are characterized by the coefficients and . In this section we provide a way to, given a polynomial with value set of cardinality , generate more polynomials with value sets of the same cardinality . For a fixed , we define a relation in the set of all polynomials of the form relating the pair of coefficients expressed as powers of a primitive root .
Polynomials over finite fields with value sets of maximum size are permutation polynomials and have many applications as we mentioned before. Polynomials with minimal value sets are also of interest (Borges & Concei ̧ca ̃o, 2013).
Definition 3.1. Consider , and let
be two polynomials over with . We say if and only if and , where is a primitive root of and .
Example 3.2. Let . Then . Now for some . Therefore and so on.
Note that is defined in a way that allows us to construct polynomials related to each other. Given a polynomial , it is easy to construct such that . This relation is fundamental in our results and, as the following lemma states, it partitions the set .
Lemma 3.3. The relation in Definition 3 is an equivalence relation in .
Proof. We will prove that the relation is reflexive, symmetric and transitive:
- Let . Then and . Therefore and is reflexive.
- Suppose that . Then, for we have that for some . Note that and . This implies that . Therefore and the relation is symmetric.
- Suppose that and . Then, for , we have that , and , for some . Note that , , hence and the relation is transitive.
We denote by the equivalence class that contains the polynomial . Using the equivalence relation we can express our results in a very concise way. The next theorem states that any two polynomials related by must have value sets of the same cardinality.
Theorem 3.4. Suppose that . Then .
Proof. First, note that for all pairs . Therefore we must have that . Let be a primitive root of the finite field. Now for any , . Let , where , and , . Then
In general, for each term of there exists a corresponding term of .
Let be given by
. Suppose that where
. Then we have that and (1) imply that . Therefore is one to one.
Now consider an element . Then for some and . Note that the correspondence between and gives a bijection between and . Therefore .
Example 3.5. From Example 3.2 we have that . Therefore .
Theorem 3.4 gives us a way to construct a polynomial with value set of cardinality , given a polynomial with value set of cardinality . In particular, given a permutation polynomial of of the form we can construct another permutation polynomial of . We state this formally in the following corollary.
Corollary 3.6 Suppose is a permutation polynomial of and that . Then is also a permutation polynomial of .
All the polynomials in an equivalence class of under the relation have value sets of the same cardinality. The next result tells the number of polynomials in each equivalence class.
Proof. Suppose that , . Note that we can obtain the elements of applying the transformation multiple times. Now note that:
Note that if , for some and for some . We just have to see that is the smallest integer such that this occurs.
Suppose there exists such that and . This implies that , and , this is only possible if is a multiple of and . Therefore is the smallest integer such that this happens.
This implies that all elements in the chain with are different and therefore we must have that .
Figure 1: The set of equivalence classes of with . All pairs of coefficients in a cell are related by . Note that the number of pairs in each cell is . The polynomials associated to the elements in a cell have value sets of the same cardinality. The cardinality of the value sets associated to different cells might or might not be equal.
Example 3.8. Consider Example 3 again where . Note that and the elements of are:
It is important to note that the result given in Proposition 1 does not depend on , only on the chosen and . Using Proposition 1 we can partition the set of polynomials of the form into equivalence classes, each of cardinality . Moreover, using Theorem 3 we can say that all of the polynomials in the same equivalence class have value sets of equal cardinality. Given a polynomial with value set of cardinality , we can combine our previous results to provide more polynomials with value set of cardinality . Although we cannot say if these are all of the polynomials that have a value set of cardinality , we know that if there exists another polynomial with value set of cardinality , there exists at least more. This leads to our main result.
Theorem 3.9. The number of polynomials with
is a multiple of .
Proof. Fix , and . Consider the set of all polynomials of the form . If there are no polynomials in with value set of cardinality , we are done. Let be such that . Using Theorems 3.4 and 3.7 we can construct more polynomials , such that .Note that for each polynomial in with value set of cardinality we may repeat the process above and obtain up to polynomials in with value set of cardinality . By counting the polynomials it is easy to see that we will have a multiple of , which proves the theorem.
Theorem 3.9 states that for any given value set of cardinality , the amount of polynomials with value sets of that cardinality will always be a multiple of . Recall that we are interested in providing ways to construct permutation polynomials, hence we are interested in the particular case when .
Corollary 3.10 For any the number of permutation polynomials of of the form is a multiple of .
In summary, we provide a straightforward way to construct up to
polynomials of the form with value set of cardinality , given a polynomial of the form with value set of cardinality . Moreover, we proved that the amount of polynomials of the form with value set of cardinality will always be a multiple of . In particular, these results hold when we are given a permutation polynomial of the form .
This research has been supported by a grant from the Center of Undergraduate Research in Mathematics (CURM) from Brigham Young University, NSF grant #DMS-1148695, and was conducted under the direction of Prof. Ivelisse Rubio, Department of Computer Science, and Prof. Francis Castro, Department of Mathematics, University of Puerto Rico, Río Piedras.
Borges, H., & Concei ̧ca ̃o, R. (2013). On the characterization of minimal value set polyno- mials. Journal of Number Theory, 133, 2021–2035.
Laigle-Chapuy, Y. (1988). When does a polinomial over a finite field permute the elements of the field? The American Mathematical Monthly, 95, 243-246.
Lidl, R., & Mullen, G. (2013). On the characterization of minimal value set polynomials. Journal of Number Theory, 133, 2021–2035.
Panario, D., & Mullen, G. (2013). Handbook of finite fields. CRC Press.
Wan, D., & Lidl, R. (1991). Permutation polynomials of the form xrf(x(q−1)/d) and their
group structure. Monatshefte fu ̈r Mathematik, 112, 149-163.
Zieve, M. (2009). On some permutation polynomials over fq of the form xr ∗h(x((q−1)/d))).
Proc. Amer. Math. Soc., 137, 2209-2216
Revista [IN]Genios, Volumen 1, Número 1 (septiembre, 2014).
ISSN#: 2324-2747 Universidad de Puerto Rico, Río Piedras
© 2014, Copyright. Todos los derechos están reservados.