<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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 M<sc>agma</sc> on numbers of up to 7000 decimal digits and collect data to show the advantages over previous implementations in practice.</p></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.

A strategy for elliptic curve primality proving

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"A strategy for elliptic curve primality proving"}

This paper deals with an implementation of the elliptic curve primality proving (ECPP) algorithm of Atkin and Morain. As the ECPP algorithm is not...

A strategy for elliptic curve primality proving

Pubblicato online: 22 gen 2016

Pagine: 125 - 142

Ricevuto: 16 nov 2015

Accettato: 13 dic 2015

DOI: https://doi.org/10.1515/ausi-2015-0015

© 2015 Gyöngyvér Kiss, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.