Primality proofs with elliptic curves: Heuristics and analysis

Abstract. This paper deals with the heuristic running time analysis of the elliptic curve primality proving (ECPP) algorithm of Atkin and Morain. Our aim is to collect assumptions and the fastest possible algorithms to reduce the heuristic running time and to show that under these assumptions and some plausible conditions the heuristic running time can be reduced down to \(o(\ln^4 n)\) bit operation for input possible prime \(n\).