Tests for Permutation Polynomials
Joachim van zur Gathen · SIAM Journal on Computing · 1991
If $\mathbb{F}_q $ is a finite field and $f \in \mathbb{F}_q [x]$, then f is called a permutation polynomial if the mapping $\mathbb{F}_q \to \mathbb{F}_q $ induced by f is bijective. This property can be tested by a probabilistic algorithm whose number of operations is polynomial (in fact, essentially linear) in the input size, i.e., in $\deg f \cdot \log q$. This is extended to “almost permutation polynomials,” whose value set consists of almost all elements of $\mathbb{F}_q $.