Wei Dai writes:
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.
If you work in GF(2^m), you can use a normal basis representation which allows you to do much faster math. Squaring, for example, becomes a simple rotation. There are also very efficient algorithms for computing inverses and solving quadratics. These speedups currently account for most of the performance improvements which elliptic curve systems offer over their integer-field counterparts. - Mark - -- Mark Chen 415/341-5539 chen@chen.com D4 99 54 2A 98 B1 48 0C CF 95 A5 B0 6E E0 1E 1D