Ce rapport décrit la théorie et
l'implantation de l'algorithme ECPP (pour <I>Elliptic Curve
Primality Proving</I>). Nous rappelons entre autres les relations
existant entre
la repr&eacute;sentation des nombres premiers par des formes quadratiques
et la construction explicite du corps de classe d'un corps quadratique
imaginaire~; la th&eacute;orie des courbes elliptiques &agrave;
multiplication complexe sur le corps des complexes et sur un corps
fini. Nous utilisons cette th&eacute;orie pour concevoir un algorithme de
preuve de primalit&eacute; tr&egrave;s efficace. La moiti&eacute; du papier est
consacr&eacute;e &agrave; la description de son implantation. En
particulier, nous donnons les meilleurs algorithmes connus 
pour acc&eacute;l&eacute;rer chaque partie du
programme. Les r&eacute;sultats obtenus sont impressionnants. Nous sommes
en mesure de prouver la primalit&eacute; d'entiers de 100 chiffres en
moins de cinq minutes sur un SUN 3/60, et nous pouvons traiter tous
les entiers de moins de 1000 chiffres en un temps raisonnable en
utilisant une implantation distribu&eacute;e.