From: Wei Dai <weidai@eskimo.com>
Date: Fri, 30 Aug 1996 07:37:26 +0800
To: Tom Rollins <trollins@interactive.visa.com>
Subject: Re: Elliptic Curve Y**2 = x**3 + a * x**2 + b
In-Reply-To: <199608291905.PAA16350@rootboy.interactive.visa.com>
Message-ID: <Pine.SUN.3.95.960829124919.16763B-100000@eskimo.com>
MIME-Version: 1.0
Content-Type: text/plain


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