Primality proofs with elliptic curves: Experimental data

Abstract. In this paper we present experimental data to confirm the heuristics that allowed us to use refinements to reduce the heuristic running time of the elliptic curve primality proving algorithm to \(o(\ln^4 n)\). We described our implementation of the algorithm of Atkin and Morain in an earlier paper [3], where the fastest known algorithms are used for various parts and we applied heuristics and refinements to obtain the improved running time. Here we justify the heuristics with practical data.