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.