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

Justin Card wrote:

I can't remember the elliptic curve system well, but if the parameters of the curve are not standard for everyone (which I am afraid they are) one method is to pick the point first, then solve for the a & b.

If this is not the case, finding the square root may be nice or tricky.

if p=3 mod 4, then the sqrt is X^(P+1) mod P, where X is the number you are trying to find the sqrt of. It can be extended to X=5(mod 8) and a few others, but I'm not sure how. There is also a form for X=1 mod 4,but I can't find reference to it. Hope this helps

A security issue is selecting an elliptic curve whose order (number of points on the elliptic curve) is divisible by a large prime number. I still have to implement this selection process and thus will have my a and b selections driven by this analysis. There also could be some bandwidth savings when transmitting an elliptic curve point to transmitt just the x and the sign bit of y and let the receiver reconstruct the actual y value. The choice for prime p could have overall speed benefits by selecting a p=3 mod 4 that makes the math simpler. This was also in Wei Dai's ModularSquareRoot C++ code "if(p%4 == 3) return a_exp_b_mod_c(a, (p+1)/4, p);" -tom -- Tom Rollins <trollins@interactive.visa.com>