A deterministic test for permutation polynomials (Q1207336)

A deterministic algorithm is presented for testing whether a given polynomial of degree \(n\) over the finite field \(F_ q\) of order \(q\) is a permutation polynomial of \(F_ q\). The algorithm requires \(O((nq)^{6/7+\varepsilon})\) arithmetic operations in \(F_ q\). For \(q\leq 4n^ 6\) it suffices to use a test due to \textit{J. von zur Gathen} [SIAM J. Comput. 20, 591-602 (1991; Zbl 0733.11048)]. For \(q>4n^ 6\) a new test is developed, the proof of which depends on the bound of \textit{E. Bombieri} [Am. J. Math. 88, 71-105 (1966; Zbl 0171.415)] for exponential sums along curves over finite fields.