Re: Elliptic Curve Y**2 = x**3 + a * x**2 + b

[chen@chen.com (Mark Chen)]

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