zbMATH — the first resource for mathematics

A strategy for elliptic curve primality proving. (English) Zbl 1345.11089
Summary: This paper deals with an implementation of the elliptic curve primality proving (ECPP) algorithm of A. O. L. Atkin and F. Morain [Math. Comput. 61, No. 203, 29–68 (1993; Zbl 0792.11056)]. 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.
11Y11 Primality
11G05 Elliptic curves over global fields
ECPP; Magma
Full Text: DOI
[1] A. O. L. Atkin, F. Morain, Elliptic curves and primality proving, Math. Comp.61, 203 (1993) 29-68. ⇒125, 128, 129 · Zbl 0792.11056
[2] W. Bosma, J. Cannon, C. Playoust, The Magma algebra system I: the user language, J. Symbolic Comput., 24, 3 (1997) 235-265. ⇒126 · Zbl 0898.68039
[3] W. Bosma, E. Cator, A. Járai, Gy. Kiss, Primality proofs with elliptic curves: heuristics and analysis, Ann. Univ. Sci. Budapest. Sect. Comput., in print ⇒ 126, 127, 129, 130, 131, 132
[4] G. Farkas, G. Kallós, Gy. Kiss, Large primes in generalized pascal triangles, Acta Univ. Sapientiae, Informatica3, 2 (2011) 158-171. ⇒126 · Zbl 1301.05015
[5] A. Járai, Gy. Kiss, Finding suitable paths for the elliptic curve primality proving algorithm, Acta Univ. Sapientiae, Informatica5, 1 (2013) 35-52. ⇒126
[6] A.K.Lenstra, H.W. Lenstra, Jr., Algorithms in number theory, in: Handbook of Theoretical Computer Science, Vol. A. Algorithms and Complexity (ed. J. van Leeuwen), Elsevier, 1990, pp. 673-716. ⇒125, 127 · Zbl 0900.68250
[7] F. Morain, Implementing the asymptotically fast version of the elliptic curve primality proving algorithm, Math. Comp.76, 257 (2007) 493-505. ⇒125, 126 · Zbl 1127.11084
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.