This report describes the theory and implementation
of the Elliptic Curve Primality Proving algorithm -- ECPP --
algorithm. This includes the relationships between representing primes
by quadratic forms and the explicit construction of class fields of imaginary
quadratic fields; the theory of elliptic curves with complex
multiplication over the field of complex numbers as well as over
finite fields. We then use this theory to design a very powerful
primality proving algorithm. Half of the paper is devoted to the
description of its
implementation. In particular, we give the currently best algorithms to
speed up each part of the program. The resulting program is very fast.
We can prove the primality of 100-digit numbers in less than five
minutes on a SUN 3/60 workstation, and we can treat all numbers with
less than 1000 digits in a reasonable amout of time using a distributed
implementation.