Permutations of the elements of $\mathbb Z_p$ Let $p$ be prime. Describe all permutations $\sigma$ of the elements of $\mathbb Z_p$, having the property that $\{\sigma(i)-i: i\in\mathbb Z_p\}=\mathbb Z_p$

(Added by Robert Lewis in an attempt to provide background, motivation, and other context for this engaging problem)
This problem essentially asks for a method of representing permutations $\sigma$ of the finite field $\Bbb Z_p$ which respects the algebraic structure/computations inherent in such fields.
 A: We use the OEIS method.  First observe that the problem makes sense even if $p$ is not prime.  Let $a_n$ denote the number of permutations $\pi$ of the ring $R=\mathbb{Z}/n\mathbb{Z}$ such that $\{\pi(x)-x\mid x\in R\}=R$.  Direct calculation for small $n$ shows that $a_n=0$ if $n$ is even; for odd $n$ we get the sequence $1,3,15,133,2025,\ldots$
This sequence appears in OEIS as A006717, which contains more terms and some references.  In particular, we find this page, which gives the nice interpretation of $a_n$ as the number of non-attacking semi-queens on an $n\times n$ toroidal chessboard.  (A "semi-queen" can only attack along diagonals of slope $1$ (not $-1$).)  No closed form appears to be known.
A: Let $\Bbb F$ be any finite field of characteristic $p$ a prime; as is well-known, $\vert \Bbb F \vert = p^n$ for some $n \in \Bbb N$, the natural numbers.  We begin with the following
Proposition: Any function $g:\Bbb F \to \Bbb F$ may be represented by a polynomial $p_g(x) \in \Bbb F[x]$.  
Proof: We use Lagrange interpolation.  Letting the elements of $\Bbb F$ be denoted by $f_0 = 0, f_1 = 1, f_2, \ldots, f_{q - 1}$, we define the polynomials $\lambda_i(x) \in \Bbb F[x]$, $0 \le i \le q -1$, via
$\lambda_i(x) = \prod_{j = 0, j \ne i}^{j = q - 1}\dfrac{x - f_j}{f_i - f_j}; \tag{1}$
it is easily seen that
$\lambda_i(f_k) = 0, k \ne i , \tag{2}$
since a factor of $f_k - f_k = 0$ will occur as one of the numerators in the product
$\lambda_i(f_k) = \prod_{j = 0, j \ne i}^{j = q - 1}\dfrac{f_k - f_j}{f_i - f_j}; \tag{3}$
also, 
$\lambda_i(f_i) = \prod_{j = 0, j \ne i}^{j = q - 1}\dfrac{f_i - f_j}{f_i - f_j} = 1. \tag{4}$
We now see that the polynomial
$p_g(x) = \sum_0^{q -1} g(f_i) \lambda_i(x) \tag{5}$
satisfies
$p_g(x) = g(x) \tag{6}$
for all $f_k \in \Bbb F$, since
$p_g(f_k) =  \sum_0^{q -1} g(f_i) \lambda_i(f_k) = g(f_k), \tag{5}$
using (2) and (4).  QED.
To be continued . . . 
A: These are known as complete mappings of the finite field $\mathbb{F}_{p}$. I think you will find that it is quite a difficult problem to describe all such permutations.
Here is a good overview:
Niederreiter, Harald; Robinson, Karl H., Complete mappings of finite fields, J. Aust. Math. Soc., Ser. A 33, 197-212 (1982). ZBL0495.12018.
You will see that this is very dependent on $p$, for example when $p=7$
we have $\pm {(x+a)}^{4} +3x + b$
giving examples for any choice of $a,b \in \mathbb{F}_{7}$; but finding and describing such polynomials relies on ad-hoc methods.
A: Take all linear polynomials of the form  $f(x) = ax+b$ with $a=2,3,\ldots p-1$ and $b=0,1,2,\ldots p-1$. Then $f(x)-x$ is also a non-constant linear polynomial and hence has a unique zero, hence fixed point for $f$. As $a$ is coprime to $p$ these functions are bijective and provide permutations as desired.
