Elliptic Curve Factorization
Date: 02/10/2006 at 12:30:33 From: John Subject: Elliptic Curve Factorization I would like to find out how to develop the parameters of a cubic parabola in general so that I can implement an integer factorization method. An example that I see often is Y^2 = X^3 - 10X - 7, where -10 < Y < 10 and -10 < X < 10 shows a nice contour. My example is (48607 + 393300*Y + 30*X)(900*X^2 - 5610*X - 79691 + 900*Y) where -2000 < Y < 200 and -30 < X < 30 also shows a nice contour. I would like to know how to add points such as P+P and P+Q. I have tried to apply the same methods that are shown in the Y^2 = X^3- a*X + b example to obtain the coordinate P+Q at [x3,y3] but have not succeeded. The process seems very straightforward but I'm missing something somewhere. I know that a lot has been written about elliptic curve factorization but I have not seen any example that treats the general case where a*X^3 + b*X^2 + c*X + D + e*Y^2 + f*X*Y + g*Y + h*X^2*Y + i*Y^2*X can then be broken down into simpler curves and used accordingly. Any solution process or reference texts would be greatly appreciated. I am largely self-taught in this area.
Date: 02/10/2006 at 16:48:21 From: Doctor Vogler Subject: Re: Elliptic Curve Factorization Hi John, Thanks for writing to Dr. Math. Adding two points on any cubic equation is fairly straight-forward. You'll see some of this worked out in Cubic Diophantine Equation in Three Variables http://mathforum.org/library/drmath/view/66650.html Suppose you have a polynomial function in two variables f(x, y) where the total degree (that of x plus that of y) in each term of the polynomial is no bigger than 3. Your elliptic curve is f(x, y) = 0. You also have to have one point on the curve (or one solution to the equation). If you want to have rational points, then you need to start with a rational point (and not every cubic polynomial has a rational root). If you want to have points in some finite field, then you can start with a point in that field. Furthermore, there are points at infinity. A point at infinity is written projectively as (a, b, 0) (with a and b not both zero, and two such points are the same point if the ratio a:b is the same; you should think of this as a direction in the plane, or the slope b/a of a line), and essentially this means that f(ax, bx) is a polynomial of degree less than three. An elliptic curve in Weierstrass form f(x, y) = y^2 - (x^3 + ax^2 + bx + c) has the point at infinity (0, 1, 0), as you can verify. In any case, you need to choose one point on your elliptic curve to be the identity point, that is, the zero point. I will call it O (the letter O) to conform to usual notation. For an elliptic curve in Weierstrass form, it is customary to take O = (0, 1, 0), which has some special properties, but this is not necessary; it need not even be a point at infinity. To add two points on an elliptic curve, first you need to know how to get the third point of intersection of a line containing two points. Some call this "multiplying" points on the elliptic curve, although this multiplication does not relate to addition on the curve in the usual way (e.g. no distribution law, and so on). You probably know how to find the line that goes through two points. Write that in the form y = mx + b or x = ny + a and then substitute into your function f(x, mx + b) or f(ny + a, y) and find all three roots of the resulting cubic polynomial. Two of the roots will be the x (or y) values of the points you started with. The third point is the x (or y) value of the "product" of your two points. Use this in the equation for your line to get the other coordinate. When your cubic polynomial is, in fact, only quadratic, so there are only two roots, then the result is a point at infinity, which you can read off the slope of the line; the line ax + by = constant goes through the point at infinity (a, b, 0). Similarly, if you want to add a normal point to a point at infinity (a, b, 0), then you take the line ax + by = constant where you choose the constant so that this line goes through the normal point. What if you start with two identical points (a, b) and (a, b)? Many lines go through both! Well, then you need the tangent line to the curve at that point, whose slope is -f_x(a,b)/f_y(a,b) where f_x and f_y represent the partial derivatives of f with respect to x and y, respectively. More precisely, you take the line f_x(a,b)*(x-a) + f_y(a,b)*(y-b) = 0. Then when you intersect this with your function, you will get a double root at (a, b), and the third root is the "product". The above method is known as the "chord and tangent method." The chord refers to the line through two points, and the tangent refers to multiplying a point by itself. So now you know how to take the "product" of two points. To add the points A and B, you take the product of A and B, and then you take the product of this result with O. To take the negative of A, you take the product of O with O, and then you take the product of this result with A. It turns out that the point O = (0, 1, 0) on a Weierstrass curve has the special property that OO = O, so the negative can be simplified by saying that it is the product of O and A. Furthermore, in this case where OO = O, the product of A and B is, in fact, the negative of the sum A + B. There is an example worked out in the page I referenced earlier. By the way, all of the stuff with "points at infinity" can be made very natural by using projective coordinates (instead of normal or "affine" coordinates), which I only hinted at. In projective space, points at infinity are just like normal points, and the above process fits in that context very naturally. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.