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

Hello all,

I have a math question concerning implementation of elliptic
curve systems. In coding some elliptic curve source, I
need to pick a random point on the following elliptic
curve in field F_p where p is a prime number.

       Y**2 = x**3 + a * x**2 + b
       where 4a**3 + 27b**2 is not equal to 0 mod p

In selecting a random point, I pick a random value for
x in the range 0 < x < p, compute the right hand side
of the equation and find myself needing to take the
square root for the two solutions.

Questions are:

  1: How can I take the suqare root mod p ?

  2: How to determine if a solution exists for a
     selected value of x ?

  3: Is the a simpler method than find a square root ?

Thanks for any ideas you may have about this...
-tom

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

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

Tom Rollins wrote:
> 
> Hello all,
> 
> I have a math question concerning implementation of elliptic
> curve systems. In coding some elliptic curve source, I
> need to pick a random point on the following elliptic
> curve in field F_p where p is a prime number.
> 
>        Y**2 = x**3 + a * x**2 + b
>        where 4a**3 + 27b**2 is not equal to 0 mod p
> 
> In selecting a random point, I pick a random value for
> x in the range 0 < x < p, compute the right hand side
> of the equation and find myself needing to take the
> square root for the two solutions.

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

-- 
  Wyntermute   
     -----BEGIN GEEK CODE BLOCK-----
     Version: 3.1
     GE d@ s++:+ a? C++++ UL++ P+ L++ E W+++ N+++ o? K--? w !O M-- V?
PS+++
     PE++ Y+ PGP++ t+++ !5 X+++ R++* tv++ b+++ DI++ D++ G++ e h r- !y 
     ------END GEEK CODE BLOCK------

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>