On Thu, 29 Aug 1996, Tom Rollins wrote:
Questions are:
1: How can I take the suqare root mod p ?
Here's some C++ code for taking modular square roots: Integer ModularSquareRoot(const Integer &a, const Integer &p) { if (p%4 == 3) return a_exp_b_mod_c(a, (p+1)/4, p); Integer q=p-1; unsigned int r=0; while (q%2==0) // while q is even { r++; q >>= 1; } Integer n=2; while (Jacobi(n, p) != -1) ++n; Integer y = a_exp_b_mod_c(n, q, p); Integer x = a_exp_b_mod_c(a, (q-1)/2, p); Integer b = (x.Square()%p)*a%p; x = a*x%p; Integer tempb, t; while (b != 1) { unsigned m=0; tempb = b; do { m++; b = b.Square()%p; if (m==r) return Integer::ZERO; } while (b != 1); t = y; for (unsigned i=0; i<r-m-1; i++) t = t.Square()%p; y = t.Square()%p; r = m; x = x*t%p; b = tempb*y%p; } assert(x.Square()%p == a); return x; }
2: How to determine if a solution exists for a selected value of x ?
The Jacobi symbol tells you whether x has a square root mod p: // if b is prime, then Jacobi(a, b) returns 0 if a%b==0, 1 if a is // quadratic residue mod b, -1 otherwise // check a number theory book for what Jacobi symbol means when b is not // prime int Jacobi(const Integer &aIn, const Integer &bIn) { assert(bIn[0]==1); Integer b = bIn, a = aIn%bIn; int result = 1; while (!!a) { unsigned i=0; while (a[i]==0) i++; a>>=i; if (i%2==1 && (b%8==3 || b%8==5)) result = -result; if (a%4==3 && b%4==3) result = -result; swap(a, b); a %= b; } return (b==1) ? result : 0; }
3: Is the a simpler method than find a square root ?
I don't think so. Let me know if you do find one. Wei Dai