The algebraic formula for the unit circle is centered at the origin is:
$$x^2+y^2=1$$
This equation is easy to generalize to any field. I'm interested in the unit circle for modular fields. Specifically, given a base $n$, we can define the unit circle $C_n$ as the set of points
$$C_n=\{(x,y)\in \mathbb{Z}^2\;\vert\; x^2+y^2\equiv 1 \mod n \}$$
What's the fastest way to compute a list of all the points in the set $C_n$ (restricting ourselves to $x$ and $y$ being in the range $[0,n-1]$)? Are there any methods that run faster than $O(n^2)$?
The parametric solution $$x = \frac{2s}{s^2+1}, \ y = \frac{s^2-1}{s^2+1} $$ works over any field (for $s$ such that $s^2+1 \ne 0$, of course). Only $x=0, y=1$ is not covered by this. This lets you enumerate all the solutions over any finite field in time linear in the cardinality (assuming each arithmetic operation in the field takes $O(1)$ time).