×

Primality proving using elliptic curves: An update. (English) Zbl 0908.11061

Buhler, J. P. (ed.), Algorithmic number theory. 3rd international symposium, ANTS-III, Portland, OR, USA, June 21–25, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1423, 111-127 (1998).
Übersicht über neuere Entwicklungen zum Thema ECPP (elliptic curves primality proving), in die Wege geleitet ursprünglich von S. Goldwasser und J. Kilian [Proc. 18th STOC, 316-329 (1986)] sowie A. Atkin and F. Morain [Math. Comput. 61, 29-68 (1993; Zbl 0792.11056)]. Die Fortschritte betreffen Implementierung, Parameterwahl und die Konstruktion von elliptischen Kurven mit komplexer Multiplikation vorgegebener Punktezahl \(\text{mod }p\) [H. Stark, Rocky Mt. J. Math. 26, 1115-1138 (1996; Zbl 0883.11026)].
Eine Laufzeitabschätzung ist offenbar (noch) nicht bekannt; Erfahrungswerte zeigen, daß ECPP langsamer zu sein scheint als der Galois-Theorie-Primzahltest, das einzige konkurrierende deterministische Verfahren für beliebige sehr große Zahlen. Allerdings scheint ECPP diesem als Beweis- bzw. Kontrollverfahren überlegen zu sein.
For the entire collection see [Zbl 0891.00022].

MSC:

11Y11 Primality
11G05 Elliptic curves over global fields
14H52 Elliptic curves
11A51 Factorization; primality

Software:

ECPP
PDFBibTeX XMLCite