Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

and I will try to explain it.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Algorithms
College Modern Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search