From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Elliptic curves equations
Date: 18 Jan 1995 17:20:43 GMT

In article <3fj9qb$nu0@lute.gcr.com>, Mark W Winstead <mwwinst@gcr.com> wrote:
>I am looking for the precise definition of an elliptic curves.  Also, as 
>some of you know, you can define a group off an elliptic curve.  I would 
>also like to have the equations for adding two points on an elliptic 
>curve to get their sum.

Come now, this one's too fun just to look up. Given two points A and  B
on the curve, draw the line through them. It meets the curve in one more
point C on the curve. Then the group law is defined by  A+B+C=0. (If  A=B
you use the tangent line through  A  instead). Do this intelligently and
it's not so bad. If the curve sits in the affine plane over a field, the
line in question is the set of points of the form  tA + (1-t)B. Now if the
elliptic curve is the solution to a cubic polynomial f, the third point  C
is found by asking that  f(tA+(1-t)B)=0. This is a cubic polynomial in t,
and you already know it has roots   0  and  1, so there's not much left
to compute: f(tA+(1-t)B)=t(t-1)(dt+f). Then  C  is  (-f/d)A + (1+f/d)B.

You might try this on curves in the simple form
	f = -y^2 + x^3 + M x + N;
here the origin is the point at infinity, so you find that the negative of
(x,y) in the group is the point (x,-y). Writing  A=(x1,y1) and B=(x2,y2)
you should get the coordinates of  C = -(A+B) to be
	x3= -(x1+x2) + m^2             y3=y1+m(x3-x1)
where  m = (y2-y1)/(x2-x1) if  A  and  B  are distinct, and
m = (3 x1^2 + M)/(2 y1)  if  A=B.

Inasmuch as the highly-rated Elliptic Curve Method for factoring large
integers relies heavily on repeating this calculation over and over
(and over and over), it is highly desirable to do the computations with as
few machine cycles as possible. Quite a bit of work has been done in this
direction during the 1980's and early 1990's. Montgomery has, I think,
taken this work to the limit.

dave

==============================================================================

From: hale@mailhost.tcs.tulane.edu (Bill Hale)
Newsgroups: sci.math
Subject: Re: Elliptic curves equations
Date: Wed, 18 Jan 1995 20:04:08 +0000

 In article <3fj9qb$nu0@lute.gcr.com>, Mark W Winstead <mwwinst@gcr.com> wrote:
 >I am looking for the precise definition of an elliptic curves.  Also, as 
 >some of you know, you can define a group off an elliptic curve.  I would 
 >also like to have the equations for adding two points on an elliptic 
 >curve to get their sum.

You might want to look at the book "Rational Points on Elliptic Curves" by
Joseph H. Silverman and John Tate in the "Undergraduate Texts in Mathematics"
series.

--
Bill Hale