Tests for permutation functions (Q1344091)

For \(q\) a prime power, let \(\mathbb{F}_ q\) denote the finite field of order \(q\) and let \(f\in \mathbb{F}_ q (x)\) be a rational function over \(\mathbb{F}_ q\). \(D\subseteq \mathbb{F}_ q\) will denote the domain of definition of \(f\). In recent years many papers have been written concerning permutation polynomials over \(\mathbb{F}_ q\), i.e. permutations which are induced by polynomials over \(\mathbb{F}_ q\). In this paper the authors consider several more general settings and study three notions of permutation function: (i) \(f\) is a permutation of \(\mathbb{F}_ q\); (ii) \(f\) is a permutation on \(D\); (iii) \(f\) is injective on \(D\). The paper contains many detailed results concerning each of these notions of permutation function as well as their inter-connections. In particular for each of them, a random polynomial-time algorithm test is presented. In addition, for the image or value set size of an arbitrary rational function, a fully polynomial-time randomized approximation scheme is given. Finally the paper concludes with a list of five open questions.