THE COMPUTATIONAL-COMPLEXITY OF RECOGNIZING PERMUTATION FUNCTIONS

Let F-q be a finite field with q elements and f is an element of F-q(x ) a rational function over F-q. No polynomial-time deterministic algor ithm is known for the problem of deciding whether f induces a permutat ion on F-q. The problem has been shown to be in co-R subset of or equa l to co-NP, and in this paper we prove that it is in R subset of or eq ual to Np and hence in Zpp, and it is deterministic polynomial-time re ducible to the problem of factoring univariate polynomials over F-q. B esides the problem of recognizing prime numbers, it seems to be the on ly natural decision problem in ZPP unknown to be in p. A deterministic test and a simple probabilistic test for permutation functions are al so presented.