Modular square root

[Paul Zimmermann]

> Date: Tue, 15 May 2007 20:03:05 +0200
> From: "Steven Beeckman" <steven.beeckman at gmail.com>
> 
> Hi,
> 
> is there an algorithm (implemented in C or C++ using GMP) available which
> calculates the square roots of (a mod p) where p is a prime? I've tried
> implementing it using GMP, but I'm lost in the cases where p != 3 mod 4 or p
> != 5 mod 8.
> 
> Thanks in advance,
> 
> Steven

You can use Cantor-Zassenhaus' algorithm:

1) generate a random residue b mod p
2) compute q = (x+b)^((p-1)/2)
3) compute gcd(q-1, x^2-a)
4) if the gcd has degree 1, its root is a solution, otherwise go to 1)

Example with a well-known Computer Algebra System:

> p:=nextprime(10^50);
           p := 100000000000000000000000000000000000000000000000151

> a:=rand(p)();
            a := 81321110693270343633073697474256143562913055018786

> b:=rand(p)();                           
            b := 86146486307198155590763466429392673708089337680673

> q:=Powmod(x+b, (p-1)/2, x^2-a, x) mod p;
            q := 228661163187034507715325999697722832371031852329 x

> Gcd(q-1, x^2-a) mod p;                  
            x + 85671386602160286586878847045001646726672507054738

> 85671386602160286586878847045001646726672507054738^2 - a mod p;
                                       0

Paul Zimmermann