When Do Power Maps Permute the Half-System Modulo a Prime?

SummaryLet p be an odd prime and let P=(p−1)/2. We study the power map ϕk as a nonlinear analogue of the Zolotarev map on the half-system H={1,…,P}. Unlike multiplication by a constant, exponentiation does not always permute H. We give a complete characterization of when ϕk is a permutation of H, and in the case where it is not surjective, we determine the exact size of its image.