A strategy for elliptic curve primality proving

Abstract

This paper deals with an implementation of the elliptic curve primality proving (ECPP) algorithm of Atkin and Morain. As the ECPP algorithm is not deterministic, we are developing a strategy to avoid certain situations in which the original implementation could get stuck and to get closer to the situation where the probability that the algorithm terminates successfully is 1. We apply heuristics and tricks in order to test the strategy in our implementation in Magma on numbers of up to 7000 decimal digits and collect data to show the advantages over previous implementations in practice.

Keywords

• f.2.1
• 11y11
• 11a51
• 14h52
• ecpp
• elliptic curves
• primality proving