
Glossary: Prime Pages: Top 5000: 
An Elliptic curve is a curve of genus one,
that is a curve that can be written in the form
E(a,b) : y^{2} = x^{3} + ax + b (with 4a^{3} + 27b^{2} not zero) They are called "elliptic" because these equations first arose in the calculation of the arclengths of ellipses. The rational points on such a curve form a group with addition defined using the "chord and tangent method:" That is, if the two points P_{1} and P_{2} are rational (have rational coefficients), then the line through P_{1} and P_{2} intersects the curve again in a third rational point which we call (P_{1}+P_{2}) (the negative is to make the associative law work out). Reflect through the xaxis to get P_{1}+P_{2}. (If P_{1} and P_{2} are not distinct, then use the tangent line at P_{1}.) If we then reduce this group modulo a prime p we get a small group E(a,b)/p whose size can be used in roughly the way we use the size of (Z/pZ)^{*} in the first of the classical primality tests. Let E be the order (size) of the group E: Theorem: E(a,b)/p lies in the interval (p+12sqrt(p),p+1+2sqrt(p)) and the orders are fairly uniformly distributed (as we vary a and b).So the elliptic curve primality proving algorithm (ECPP for short) has replaced the groups of order n1 and n+1 used in the classical test with a far larger range of group sizes. We can keep switching curves until we find one we can "factor". This improvement comes at the cost of having to do a great deal of work to find the actual size of these groupsbut works for all numbers, not just those with very special forms. About 1986 S. Goldwasser & J. Kilian [GK86] and A. O. L. Atkin [Atkin86] introduced elliptic curve primality proving methods. Atkin's method, ECPP, was implemented by a number of mathematicians, including Atkin & Morain [AM93]. Heuristically, ECPP is O((log n)^{5+eps}) (with fast multiplication techniques) for some eps>0 [LL90]. It has been proven to be polynomial time for almost all choices of inputs. A version attributed to J. O. Shallit may be O((log n)^{4+eps}). François Morain, who first set the record for proving primality via ECPP, has made his program available to all. More recently Marcel Martin wrote a version called Primo for Windows machines. Version of these two programs hold most of the records.
Related pages (outside of this work)
References:
Chris K. Caldwell © 19992018 (all rights reserved)
