Carlitz rank and index of permutation polynomials

DOI10.1016/J.FFA.2017.09.002MaRDI QIDQ1679707zbMATH OpenOpenAlexFDO

Authors Leyla Işık, Arne Winterhof

Publication date 21 November 2017

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.06361

zbMATH Keywords

indexcryptographydiscrete logarithmfinite fieldscharacter sumscyclotomic mappingslinearityinvertibilitypermutation polynomialsCarlitz rank

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Other character sums and Gauss sums (11T24)

Abstract: Carlitz rank and index are two important measures for the complexity of a permutation polynomial $f(x)$ over the finite field $F_q$. In particular, for cryptographic applications we need both, a high Carlitz rank and a high index. In this article we study the relationship between Carlitz rank $Crk(f)$ and index $Ind(f)$. More precisely, if the permutation polynomial is neither close to a polynomial of the form $ax$ nor a rational function of the form $a{x}^{-1}$, then we show that $Crk(f)>q-max3Ind(f),(3q{)}^{1/2}$. Moreover we show that the permutation polynomial which represents the discrete logarithm guarantees both a large index and a large Carlitz rank.

Recommendations

• On the Carlitz rank of permutation polynomials
• On the Carlitz rank of permutations of \(\mathbb F_q\) and pseudorandom sequences
• The Carlitz rank of permutations of finite fields: a survey
• Permutation polynomials with Carlitz rank 2
• Investigations of \(c\)-differential uniformity of permutations with Carlitz rank 3

Cites work

• A polynomial representation for logarithms in GF(q)
• Complete mappings and Carlitz rank
• Cryptographic applications of analytic number theory. Complexity lower bounds and pseudo\-randomness
• Cyclotomic Mapping Permutation Polynomials over Finite Fields
• Cyclotomic \(\mathcal R\)-orthomorphisms of finite fields
• Cyclotomy and permutation polynomials of large indices
• Index bounds for character sums of polynomials over finite fields
• Index bounds for value sets of polynomials over finite fields
• On the Carlitz rank of permutation polynomials
• On the Carlitz rank of permutations of \(\mathbb F_q\) and pseudorandom sequences
• Permutations in a finite field
• Polynomial interpolation of the discrete logarithm
• The Carlitz rank of permutations of finite fields: a survey

Cited in

(8)

• Permutation polynomials with Carlitz rank 2
• Permutation polynomials and factorization
• scientific article; zbMATH DE number 640564 (Why is no real title available?)
• On the Carlitz rank of permutations of \(\mathbb F_q\) and pseudorandom sequences
• The additive index of polynomials over finite fields
• On the index of the Diffie-Hellman mapping
• The Carlitz rank of permutations of finite fields: a survey
• Some classes of permutation binomials and trinomials of index \(q-1\) over \(\mathbb{F}_{q^n}\)

This page was built for publication: Carlitz rank and index of permutation polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679707)