Permutations on finite fields with invariant cycle structure on lines
- PDF / 372,694 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 205 Views
Permutations on finite fields with invariant cycle structure on lines Daniel Gerike1
· Gohar M. Kyureghyan2
Received: 3 September 2019 / Revised: 31 December 2019 / Accepted: 16 January 2020 © The Author(s) 2020
Abstract We study the cycle structure of permutations F(x) = x+γ f (x) on Fq n , where f : Fq n → Fq . We show that for a 1-homogeneous function f the cycle structure of F can be determined by calculating the cycle structure of certain induced mappings on parallel lines of γ Fq . Using this observation we describe explicitly the cycle structure of two families of permutations 1 over Fq 2 : x + γ Tr(x 2q−1 ), where q ≡ −1 (mod 3) and γ ∈ Fq 2 , with γ 3 = − 27 and 2s−1 s−1 2 +3·2 +1 s (q+1)/3 3 x + γ Tr x = 1. , where q = 2 , s odd and γ ∈ Fq 2 , with γ Keywords Permutation polynomials · Cycle structure · Switching construction · Subspaces Mathematics Subject Classification 11T06 · 05A05 · 11T71 · 12Y05 A permutation can be expressed as a unique product of disjoint cycles (up to reordering). The cycle decomposition of a permutation on a finite field provides information on both algebraic as well as combinatorial properties of the permutation. Much of that information is retained in the cycle structure of the permutation, which lists the lengths of the cycles and their frequencies in the cycle decomposition. Two permutations have the same cycle structure exactly if they lie in the same conjugacy class of the symmetric group. One of the main current challenges in the research on permutations of finite fields is finding the cycle structure for interesting families of permutation polynomials, and vice versa, given a conjugacy class of the symmetric group over a finite field, find a nice member of it. At present, the cycle structure is studied for very few families of permutation polynomials. In [1] the cycle structure of monomials x k over Fq is determined. It directly depends on the multiplicative order of the exponent k modulo the divisors of q − 1. In [10] formulas for
This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography 2019”.
B
Daniel Gerike [email protected] Gohar M. Kyureghyan [email protected]
1
Otto-von-Guericke University of Magdeburg, Universitätsplatz 2, 39106 Magdeburg, Germany
2
University of Rostock, Ulmenstraße 69, Haus 3, 18057 Rostock, Germany
123
D. Gerike, G. M. Kyureghyan
the cycle structure of Dickson polynomials Dn (x, a) with parameter a = 1 or a = −1 are given. The cycle structure of Dickson polynomials is similar to the cycle structure of monomials. In [12] the cycle structure of q-linearized polynomials over Fq n is considered. The authors give a formula for the cycle structure of the restriction of a linearized polynomial to certain subspaces of Fq n . Further they show how to combine these results to get the cycle structure on the whole field. Applying this method to a given family of linearized permutation polynomials is often challenging. However it can be used to comp
Data Loading...
