I am working on doing explicit computations finding class groups of quaternions over $\mathbb{Q}$, and the following question (with $n=3$) was a clear choking point:
Given a point $P = [x\_0, \dots, x\_n] \in \mathbb{P}^{n}(\mathbb{F}\_p)$, is there a method beyond iterating through multiples $(kx\_0, \dots, kx\_n)$ of finding integers $a\_0, \dots, a\_n$ so $[a\_0, \dots, a\_n] = P$ and so that $a\_0^2 + \dots + a\_n^2$ is minimized?


Further, is there some upper bound on this minimum norm that depends only on $p$ and $n$? There certainly is a lower bound of $\Theta(p^{2n/(n+1)})$: what is needed to turn it into an upper bound?



Finding the "minimum norm" of points in projective space above a prime field
The lifts to ${\bf Z}^{n+1}$ of a point in projective $n$-space mod $p$
constitute $L - L\_0$ where $L\_0 = p{\bf Z}^{n+1}$ and $L \supset L\_0$
is a sublattice of index $p^n$ in ${\bf Z}^{n+1}$. At least when
(as in your case) $n$ is a fixed small number and $p$ is large,
your question is thus tantamount to the Shortest Vector Problem for $L$,
which can be solved in time polynomial in $\log p$. The upper bound
$O\_n(p^{2n/(n+1)})$ is an application of Minkowski's theorem
(and the $O$-constant is absically the Hermite constant in dimension $n+1$).


**gp** code:



```
M(v,p) =  L = matrixqz(concat(p * matid(#v),v~),-1); L * qfminim(L~*L)[3][,1]

```

for example, **M([2^32,3^32,5^32,7^32], 1000003)** returns
**[-13605, 14547, -18368, 15199]** in "0 ms" ("zero milliseconds").


