Permutation polynomials and factorization
- PDF / 451,213 Bytes
- 22 Pages / 439.642 x 666.49 pts Page_size
- 69 Downloads / 209 Views
Permutation polynomials and factorization ˘ 1 ¨ Kalaycı1 · Henning Stichtenoth1 · Alev Topuzoglu Tekgul Received: 29 September 2019 / Accepted: 22 June 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We discuss a special class of permutation polynomials over finite fields focusing on some recent work on their factorization. In particular we obtain permutation polynomials with various factorization patterns that are favoured for applications. We also address a wide range of problems of current interest concerning irreducible factors of the terms of sequences and iterations of such permutation polynomials. Keywords Permutation polynomials over finite fields · Factorization of polynomials · Sequences of polynomials · Irreducible factors · Smooth polynomials · Squarefree polynomials · Primitive irreducible divisors · Carlitz rank Mathematics Subject Classification (2010) 11T06 · 11T55 · 12E20
1 Introduction Permutation polynomials over finite fields have been attracting a wide interest, not only because there are many natural (and still open) problems connected with them, but also because they have vast applications, especially in combinatorics, coding and cryptography. Let Fq be the finite field with q elements. We recall that a polynomial F ∈ Fq [x] is a permutation polynomial of Fq if the corresponding polynomial map from Fq to Fq , given by γ → F (γ ), is a permutation of Fq . In recent years, a wealth of results on various aspects of permutation polynomials have been obtained, see for instance the surveys [23, 32] and references therein.
This article belongs to the Topical Collection: Boolean Functions and Their Applications IV Guest Editors: Lilya Budaghyan and Tor Helleseth Alev Topuzo˘glu
[email protected] Tekg¨ul Kalaycı [email protected] Henning Stichtenoth [email protected] 1
Sabancı University, MDBF, Orhanlı, 34956 Tuzla, Istanbul, Turkey
Cryptography and Communications
Here, we study a special class C of permutation polynomials over Fq . We first present a survey of recent results on this class, focusing on the properties that are particularly relevant for applications in cryptography. We then focus on the factorization of polynomials in C and sequences of such polynomials. The first results on the irreducible factors of permutation polynomials have been obtained by the authors recently, see [28]. Indeed, factorization of polynomials over finite fields is a classical problem with many theoretical implications. It is also crucial for applications; in cryptography, polynomial factorization is used, for example, in number sieve algorithms for factoring integers, and in index calculus to compute discrete logarithms, see [16, 17, Chapter 15, 18, 22, 43]. Construction/design of cyclic redundancy codes is one of the instances in digital communication, where polynomials with particular types of factors are sought for. Our results enable one to obtain classes of permutation polynomials with favourable factorization patterns. We recall that a polyn
Data Loading...
