Solving Quadratic Congruences

    Consider the congruence



where is an odd prime and Inspired by completing the square, we have











Let and then we have a simplified version of the original namely;



The solvability of this equation can be determined by using the law of quadratic reciprocity.

Proposition (Shanks Algorithm) Let be a solution to let be integers such that where and is odd, and let be a quadratic nonresidue modulo Then can be found by repeating the following loop:

    (i) Set and   

    (ii) Find the least such that .

    (iii) If then the solutions are .  
    
    (iv) If set and goto (ii) and replace by and by
      

Example (Solving a Quadratic Congruence) Solve the following quadratic congruences.

(a)

    Solution.  First we find and so we set and Next we find the a quadratic nonresidue. Since we use With and we perform Shanks algorithm.
    


(b)

    Solution.  We let Since we let Also, since we let

• print this page
• pages linking here
• related pages