Elliptic Curves: Algorithms

Date: 03/11/99 at 02:35:04
From: Mark Pineda
Subject: Elliptic curve factoring 

If the family of elliptic curves is defined by y^2 = x^3 + 1, how do 
we find the number of points on the curve over F sub p?

Date: 03/11/99 at 16:24:59
From: Doctor Rob
Subject: Re: Elliptic curve factoring

Two things before we begin. First, the above equation is a single 
curve, not a family of curves. Secondly, you are asking how to find the 
number of points on this curve, but your subject is "Elliptic curve 
factoring." These two are not the same thing.

Hasse's Theorem says that if N is the number of points, then

   p + 1 - 2*sqrt(p) < N < p + 1 + 2*sqrt(p).

If p is small you can actually try all values of x, and find which ones 
give x^3 + 1 a quadratic residue modulo p. Those that do will give two 
points (x,sqrt[x^3+1]) and (x,-sqrt[x^3+1]). Those that do not will 
give no points. Of course, those that give x^3 + 1 = 0 (there are 0, 1, 
or 3 of them) will give a single point (x,0). Count them all up, and 
you will have N. If N is not in the above range, you have missed some. 
This can work for values of p up to, perhaps, 10^6.

The method to try next if p is too large to do the above, is to use the 
Shanks Baby-Step-Giant-Step Algorithm. This depends on the following. 
The points on the curve modulo p form a finite abelian group, and 
Lagrange's Theorem says that the order of the group times any element 
must be the identity.

Take a point P on the curve. (This is not too tough. Pick a value of 
x, and test whether x^3 + 1 is a square. Your chance of success is very 
close to 1/2. If not, throw that x away and try again. After just a few 
trials, you will find a successful value of x. If it is a square, find 
its square root, and let that be y, and you have your point P.) Let L 
be 2*p^(1/4), rounded up to the next integer. Compute

   P(k) = k*P, k = 1, 2, 3, ... L

Here, this involves adding points on the elliptic curve, using the 
group law for this operation in the group of points. If any of the 
P(k)'s is 0, the identity of the group, then you have found the order 
m <= L of P. If not, put these in a table and sort it. Also compute

   Q(i) = (p+1-L^2)*P + i*(L*P) for i = 0, 1, ..., L.

Put these into another table and sort it, too. Now look for a point in 
both tables. Then for each such match you have

   k*P = (p+1-L^2)*P + i*(L*P),
   O = (p + 1 - L^2 + i*L - k)*P.

This implies that the order m of the element P in the group of points 
is a divisor of p + 1 - L^2 + i*L - k, and so it is a divisor of the 
GCD of these values for each such match. It is also a divisor of N. If 
you can factor this GCD completely, you can determine the exact value 
of m; then N must be a multiple of m. If m is not too small, there will 
be a feasible number of possibilities for N in the above range, 
sometimes only one. If m is too small (and this can happen: P = (-1,0) 
has m = 2, for example), you should discard P, pick a different one, 
and try again.

If you cannot factor this GCD completely, write it in the form M*R, 
where M is completely factored, and R is composite but not factored.  
Then you can determine the smallest multiple of R that is also a 
multiple of m. It is very likely, but not sure, that m will equal this 
number. This will give you a value for N which has a small probability 
of being incorrect. This works for p up to perhaps 10^24.

If p is too large to do either of the above computations, then you 
have to resort to something called Schoof's Algorithm, which determines 
N modulo q for several small primes q, and then combines this 
information using the Chinese Remainder Theorem. If the product of 
these small primes is > 4*sqrt(p), then there is just one number in 
the above range which is in the resulting congruence class, so that 
must be N.

If you need more information about Schoof's Algorithm, write again
and I will try to explain it.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/