On the Carlitz rank of permutations of F-q and pseudorandom sequences

Domingo Gomez Perez, Alina Ostafe, Alev Topuzoglu*

*Corresponding author for this work

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

L. Carlitz proved that any permutation polynomial f over a finite field F-q is a composition of linear polynomials and inversions. Accordingly, the minimum number of inversions needed to obtain f is defined to be the Carlitz rank off by Aksoy et al. The relation of the Carlitz rank of f to other invariants of the polynomial is of interest. Here we give a new lower bound for the Carlitz rank of f in terms of the number of nonzero coefficients of f which holds over any finite field. We also show that this complexity measure can be used to study classes of permutations with uniformly distributed orbits, which, for simplicity, we consider only over prime fields. This new approach enables us to analyze the properties of sequences generated by a large class of permutations of F-p, with the advantage that our bounds for the discrepancy and linear complexity depend on the Carlitz rank, not on the degree. Hence, the problem of the degree growth under iterations, which is the main drawback in all previous approaches, can be avoided. (C) 2013 Elsevier Inc. All rights reserved.

Original languageEnglish
Pages (from-to)279-289
Number of pages11
JournalJournal of Complexity
Volume30
Issue number3
DOIs
Publication statusPublished - Jun 2014
Externally publishedYes

Keywords

  • Permutation polynomials over finite fields
  • Carlitz rank
  • Pseudorandom number generators

Cite this