Reverse Modulus Operator with given condition

Question

I have an equation: $$ x^2 \mod p = z $$ $p$ and $z$ are given. $x$, $p$ and $z$ are positive integers and a maximal value of $x$ is given (say $M$). $p$ is a prime. How can i calculate (multiple possible values) $x$ when $p$ and $z$ are known?

Answer 1

If $z$ is a quadratic residue mod $p$ you can compute a solution for odd primes with the methods given in the algorithm section of the Wiki article e.g. $$x\equiv z^{\frac{p+1}{4}} \pmod p, \quad \text{if}\quad p \equiv 3 \pmod 4$$ or with Tonelli-Shanks otherwise. Assume $x$ the least positive representative, then $p-x\;$ is the second solution. The answer which solutions are $\le M$ depends obviously on $M$. Example with $p=11, z=5:\;$ The solutions are $x_1\equiv 4 \equiv 5^3 \pmod {11},\quad x_2\equiv 7 \pmod {11},\;$ i.e. for $M\le 3$ there are no solutions, for $M\le 6$ there is one and for $M > 6$ there two solutions.