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 MAX value of x is given (say M). p is prime. How can i calculate (multiple possible values) x when p and z are known ?

UPDATE:

I found solution here:

https://math.stackexchange.com/questions/848062/reverse-modulus-operator-with-given-condition/848106#848106

Answer 1

if x^2 mod p = z
then x^2 = n*p + z for some integer n
with p and z known, substitute integer values for n to find x

Answer 2

I don't why Santosh was downvoted,but his reasoning is correct!

As x^2 mod p=z   --->>    x^2=n*p+z   // for some integer n.

As you have p and z as known in your hands,you can individually check if x^2 mod p=z as shown below in the code and then find x(or rather equate the value of x) :-

    public static void main(String[] args) {   //main-method
     int x,p,z,xMAX=10;     // as per your condition
     p=13;                         // assigned p a prime positive integer value
     z=10;                         // assigned z a positive integer value
     for(x=0;x<=xMAX;x++){
      int sq=(int)Math.pow(x,2);    // squrare of x for each loop        
          if(sq%p==z){               // comparing square-value modulus prime value with value of z to be equal
           System.out.println("One value of x possible is "+x);   // if matches,you have one solution
          }
          else continue;
     }
   }

Sorry as the code is in Java,but I have mentioned comments in the code to identify each section. Also,this is very complicated algorithm as one can have a better algorithm for it,I guess! But,the output is working fine and is correct!

Output as per code :-

One value of x possible is 6 
One value of x possible is 7