Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
College Number Theory

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/