By using primitive roots how does one solve $x^2 \equiv -1 \pmod p$ for $x$, given prime $p$. By using primitive roots how does one solve $x^2 \equiv -1 \pmod p$ for $x$, given prime $p$ (when solvable).
In particular I want to solve for very large $p$ efficiently.
 A: This uses Euler's Criterion
it is not necessary to find a primitive root. First we find a quadratic nonresidue $\pmod p.$  That is, an $a$ such that Legendre symbol
$$ ( a,p) = -1  $$
Stan Wagon points out that the search for a nonresidue is quick. This is in a column in February 1990 called The Euclidean Algorithm Strikes Again.
Then $$  a^{\frac{p-1}{2}} \equiv -1 \pmod p $$
while $\frac{p-1}{2}$ is even. Thus
$$ \left(  a^{\frac{p-1}{4}} \right)^2 \equiv -1 \pmod p $$
A: Unless you are enquiring on “how to compute” the primitive roots $\mod p$ themselves (or perhaps I’m misunderstanding your question?), then this is actually straightforward because once you already have a primitive root, say $r$ , modulo $p\equiv 1\pmod 4$, then we have $$(r^{(p-1)/4})^2\equiv-1\pmod p\,.$$
That is, $x= r^{(p-1)/4}$ is such a solution.
Added Later
In addition to VIVID’s comment below on finding a primitive root, it is perhaps worth remarking that there is no general formula for finding them; in general, for sufficiently large $p$, combing through $\{1,2,\ldots,\lfloor\sqrt{p}\rfloor\}$ is enough to find the least primitive root modulo $p$ (indeed, McGown and Trudgian (2020) have recently claimed that $p\ge 10^{56}$ suffices). It is also perhaps worth mentioning that you may also obtain a solution to your problem in $\{1,2,\ldots,p-1\}$ as $$x_0=r^{(p-1)/4}-\lfloor p^{-1}r^{(p-1)/4}\rfloor p\,.$$
