I'm looking at algorithms to construct short paths in a particular Cayley graph defined in terms of quadratic residues. This has led me to consider a variant on Lagrange's four-squares theorem.
The Four Squares Theorem is simply that for any $n \in \mathbb N$, there exist $w,x,y,z \in \mathbb N$ such that
$$
n = w^2 + x^2 + y^2 + z^2 .
$$
Furthermore, using algorithms presented by Rabin and Shallit (which seem to be state-of-the-art), such decompositions of $n$ can be found in $\mathrm{O}(\log^4 n)$ random time, or about $\mathrm{O}(\log^2 n)$ random time if you don't mind depending on the ERH or allowing a finite but unknown number of instances with less-well-bounded running time.
I am considering a Cayley graph $G_N$ defined on the integers modulo $N$, where two residues are adjacent if their difference is a "quadratic unit" (a multiplicative unit which is also quadratic residue) or the negation of one (so that the graph is undirected). Paths starting at zero in this graph correspond to decompositions of residues as sums of squares.
It can be shown that four squares do not always suffice; for instance, consider $N = 24$, where $G_N$ is the 24-cycle, corresponding to the fact that 1 is the only quadratic unit mod 24. However, finding decompositions of residues into "squares" can be helpful in finding paths in the graphs $G_N$. The only caveat is that only squares which are relatively prime to the modulus are useable.
So, the question: let $p$ be prime, and $n \in \mathbb Z_p ( := \mathbb Z / p \mathbb Z)$. Under what conditions can we efficiently discover multiplicative units $w,x,y,z \in \mathbb Z_p^\ast$ such that $n = w^2 + x^2 + y^2 + z^2$? Is there a simple modification of Rabin and Shallit's algorithms which is helpful?
Edit: In retrospect, I should emphasize that my question is about efficiently finding such a decomposition, and for $p > 3$. Obviously for $p = 3$, only $n = 1$ has a solution. Less obviously, one may show that the equation is always solvable for $n \in \mathbb Z_p^\ast$, for any $p > 3$ prime.
Best Answer
There is also an unconditional deterministic polynomial-time algorithm to find $x,y,z,w \in \mathbf{F}_p^\times$ such that $x^2+y^2+z^2+w^2=n$, given any $n \in \mathbf{Z}$ and any prime $p \ge 7$.
First, given $a,b,c \in \mathbf{F}_p^\times$, Theorem 1.10 of Christiaan van de Woestijne's thesis lets one find an $\mathbf{F}_p$-point $P$ on the smooth conic $C \colon ax^2+by^2=cz^2$ in $\mathbf{P}^2$ over $\mathbf{F}_p$. The usual trick of drawing lines through $P$ and taking the second point of intersection with $C$ lets one parametrize $C(\mathbf{F}_p)$. At most $6$ points of $C(\mathbf{F}_p)$ have one of $x,y,z$ equal to $0$, so by trying at most $7$ lines, one finds a point on the affine curve $ax^2+by^2=c$ with $x,y \in \mathbf{F}_p^\times$.
Now, to solve $x^2+y^2+z^2+w^2=n$, choose $c \in \mathbf{F}_p \setminus \{0,n\}$, and apply the previous sentence to find $x,y,z,w \in \mathbf{F}_p^\times$ satisfying $x^2+y^2=c$ and $z^2+w^2=n-c$.