[Foxtrot] Square Roots modulo 4n+1

[Alan Lawrence]

OK, found two methods on the web...not sure whether they're the same or
not. Here's the first:

---BEGIN---
Have p = odd prime, congruent to 1 mod 4, 0 < n < p, and (n/p) = +1. 
Want s such that s^2 = n (mod p). 
Put q = (p+1)/2.

     s = 1
     n = n-1
     while (n/p) = +1 {
         s = s+1
         n = (n-2s+1) mod p
         if n = 0 return             /* s is square root */
     }
     q = q/2                         /* integer division */
     v = 1
     r = s
     u = 1
     while q > 0 {
         x = (rr - nuu) mod p        /* rr = r^2, etc.   */
         u = 2ru mod p
         r = x
         if q odd {
             x = (sr - nvu) mod p
             v = (vr + su) mod p
             s = x
         }
         q = q/2
     }
     return
---END---

I'm guessing that (n/p)=+1 is a reference to the Jacobi Symbol; when it's
plus 1, n is a quadratic residue mod p, when -1 or 0 it's not.


Second algorithm:

To find root of s modulo p,

Try x=0,1,2....until you find a x such that y=(P^2)/4)-s is _not_ a
quadratic residue modulo p (i.e. until jacobiSymbol(x,p)==-1)

now sqrt s = (x/2 + 1<Z>)^((p+1)/2)

which is done by the standard exponentiation algorithm, with the
multiplication rule:

(a+b<Z>)(c+d<Z>) = ac+bdy + (ad+bc)<Z> (y having been worked out above)

Apparently, "this holds always, but sqrt(s) is real (i.e. the <Z>
component is zero) if and only if s is a quadratic residue mod p".

Not sure whether this means it works for p=3 (mod 4) or not. I could code
this up in 1/2 an hour if you want.

HTH
Alan