What Are Elliptic Curves and Why Are They Useful?

Date: 03/04/2006 at 12:53:14
From: arun
Subject: elliptic curves and related problems

What are elliptic curves?  Why are they important? 

Date: 03/04/2006 at 13:43:47
From: Doctor Vogler
Subject: Re: elliptic curves and related problems

Hi Arun,

Thanks for writing to Dr. Math.  There are many ways I could answer
this question.  But let's try this one:

In the simplest sense, curves are solution sets of polynomial
equations in two variables (say x and y).  For example, the circle

  x^2 + y^2 = 1

is a curve, as are lines, hyperbolas, and many other shapes, although
not, for example, sine waves, since these are not given by polynomial
equations.

Elliptic curves, in the simplest sense, are curves of the form

  y^2 + dxy + ey = x^3 + ax^2 + bx + c.

The reason they are important is that the solutions form an Abelian
group.  This means that you can "add" two points on the curve and get
another point on the curve.  This addition is associative, 
commutative, and has an identity and inverses.  This group law is
described in

  Cubic Diophantine Equation in Three Variables
    http://mathforum.org/library/drmath/view/66650.html 

So sometimes elliptic curves arise in Diophantine equations, which
means that you have an equation, and you want to find all integer, or
all rational, solutions.  There are methods for solving this kind of
problem on elliptic curves, whereas not all curves (or equations) can
be so solved.

Other times, they arise because they are useful groups.  For example,
there is a method for factoring numbers that uses elliptic curves and
modular arithmetic, where the elliptic curve is useful because you can
create a group from the unknown factors of your number, whose size can
vary somewhat.  See also

  Factoring Algorithms
    http://mathforum.org/library/drmath/view/65455.html 

There are related algorithms for testing and verifying that a large
number is prime using elliptic curves.  Furthermore, there are
cryptographic schemes (codes) that work on elliptic curves that are
believed to be more secure than similar codes that only use regular
modular arithmetic.

In each case, the important fact is that the elliptic curve makes a
group, and so you can use elliptic curves to come up with groups that
have desirable properties which help you solve certain kinds of problems.

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/ 

Date: 03/05/2006 at 09:50:53
From: arun
Subject: Thank you (elliptic curves and related problems)

Thanks, Doctor Vogler, for providing me such a useful piece of
information.