From: bill.daly@tradition.co.uk
Subject: Choosing curves for ECM factorization
Date: Mon, 25 Oct 1999 21:44:27 GMT
Newsgroups: sci.math.research
Keywords: elliptic curves of rank 5

Suppose that, in choosing a curve for ECM, I generate 5 random points
(x[i],y[i]) rather than one, then solve the system of equations

  y[i]^2 + a1*x[i]*y[i] + a3*y[i] = x[i]^3 + a2*x[i]^2 + a4*x[i] + a6

for (a1,a2,a3,a4,a6). Having done this, I can then perform a simple
linear transformation to come up with a curve

  y^2 = x^3 + c4*x + c6

which also has 5 randomly generated rational points on it. Unless I am
very unlucky, I would expect this curve to be of rank 5 or greater
("unlucky" meaning that the 5 randomly chosen points happen to be
linearly dependent over the curve). I would also conjecture that a curve
of rank 5 is more likely to have an order mod p which is a product of
small primes than a curve of rank 1. If this conjecture has any merit,
then it follows that using a set of curves generated in this way is more
likely to lead to a factorization than a set of curves with only one
known random point.

The cost of this, apart from the extra initialization, is that in
doubling a point, I must calculate 3x^2 + c4 rather than 3x^2 + 1 (and
of course I must store the c4 values for each curve). Without loss of
generality, one of the initially chosen points can be (0,0) (forcing a6
= 0), which simplifies the calculations somewhat.

Is this idea worth pursuing?

Regards,

Bill


Sent via Deja.com http://www.deja.com/
Before you buy.