Carlitz rank and index of permutation polynomials

DOI10.1016/J.FFA.2017.09.002zbMATH Open1430.11157arXiv1611.06361OpenAlexW2555444332MaRDI QIDQ1679707FDOQ1679707

Authors: Leyla Işık, Arne Winterhof 

Publication date: 21 November 2017

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• Permutation polynomials with Carlitz rank 2
• Permutation polynomials and factorization
• Title not available (Why is that?)
• 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
• Some classes of permutation binomials and trinomials of index \(q-1\) over \(\mathbb{F}_{q^n}\)
• The Carlitz rank of permutations of finite fields: a survey

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)