Elliptic curves and primality proving

A. O. L. Atkin, François Morain

Type: Article

Publication Date: 1993-01-01

Citations: 388

DOI: https://doi.org/10.1090/s0025-5718-1993-1199989-x

Abstract

The aim of this paper is to describe the theory and implementation of the Elliptic Curve Primality Proving algorithm. Problema, numeros primos a compositis dignoscendi, hosque in factores suos primos resolvendi, ad gravissima ac utilissima totius arithmeticae pertinere, et geometrarum tum veterum tum recentiorum industriam ac sagacitatem occupavisse, tam notum est, ut de hac re copiose loqui superfluum foret.

Locations

Mathematics of Computation - View - PDF
HAL (Le Centre pour la Communication Scientifique Directe) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Elliptic Curves for Primality Proving	2025	François Morain
+	Elliptic Curves for Primality Proving	2011	François Morain
+	Elliptic Curves for Primality Proving	2006	François Morain
+	Elliptic Curves for Primality Proving	2012
+	Implementing the asymptotically fast version of the elliptic curve primality proving algorithm	2005	François Morain
+	Primality proving using elliptic curves: An update	1998	François Morain
+ PDF Chat	Implementing the asymptotically fast version of the elliptic curve primality proving algorithm	2006	François Morain
+	Easy numbers for the elliptic curve primality proving algorithm	1992	François Morain
+	Dual Elliptic Primes and Applications to Cyclotomy Primality Proving	2007	Preda Mihăilescu
+ PDF Chat	Primality Proving with Elliptic Curves	2007	Laurent Théry Guillaume Hanrot
+	Some remarks on primality proving and elliptic curves	2014	Alice Silverberg
+	Primality tests for 2^{𝑝}±2^{(𝑝+1)/2}+1 using elliptic curves	2011	Yu Tsumura
+ PDF Chat	A strategy for elliptic curve primality proving	2015	Gyöngyvér Kiss
+ PDF Chat	Finding suitable paths for the elliptic curve primality proving algorithm	2013	Antal A. Járai Gyöngyvér Kiss
+ PDF Chat	A framework for deterministic primality proving using elliptic curves with complex multiplication	2015	Alexander Abatzoglou Alice Silverberg Andrew V. Sutherland Angela Wong
+ PDF Chat	Primality testing using elliptic curves	1999	Shafi Goldwasser Joe Kilian
+ PDF Chat	Primality proving using elliptic curves with complex multiplication by imaginary quadratic fields of class number three	2024	Hiroshi Onuki
+	Number Theoretic Properties of Elliptic Curves	2014	Marius Blomlie
+	Four primality testing algorithms	2008	René Schoof
+	Four primality testing algorithms	2008	René Schoof

Works That Cite This (222)

Action	Title	Year	Authors
+	Finding composite order ordinary elliptic curves using the Cocks–Pinch method	2010	Dan Boneh Karl Rubin Alice Silverberg
+ PDF Chat	On the Use of Weber Polynomials in Elliptic Curve Cryptography	2004	Elisavet Konstantinou Yannis C. Stamatiou Christos Zaroliagis
+	An approach for computing generators of class fields of imaginary quadratic number fields using the Schwarzian derivative	2020	Jay Jorgenson Lejla Smajlović Holger Then
+ PDF Chat	Separating Decision Diffie–Hellman from Computational Diffie–Hellman in Cryptographic Groups	2003	Antoine Joux Kim Thuat Nguyen
+ PDF Chat	Detecting complex multiplication	2005	Jeffrey D. Achter
+	On prime-order elliptic curves with embedding degrees k=3, 4 and 6.	2007	Koray Karabina Edlyn Teske
+	Solutions by radicals at singular values k_N from new class invariants for N \equiv 3 mod 8	2008	David J. Broadhurst
+	Failure of the Hasse principle on general K3 surfaces	2011	Brendan Hassett Anthony Várilly‐Alvarado
+	Finding composite order ordinary elliptic curves using the Cocks-Pinch method.	2009	Dan Boneh Karl Rubin Alice Silverberg
+	Computing the cardinality of CM elliptic curves using torsion points	2002	François Morain

Works Cited by This (60)

Action	Title	Year	Authors
+ PDF Chat	A new cubic character sum	1982	Ajit Rajwade J. C. Parnami
+	Modular forms and Dirichlet series	1969	A. P. Ogg
+	Introduction to the construction of class fields	1985	Harvey Cohn
+	A Classical Invitation to Algebraic Numbers and Class Fields	1978	Harvey Cohn
+	Complex multiplication of Abelian varieties and its applications to number theory	1961	五郎志村豊谷山
+ PDF Chat	Simple groups of square order and interesting sequence of primes	1980	Morris Newman Daniel Shanks H. H. Williams
+ PDF Chat	Primes of the form 𝑛!±1 and 2⋅3⋅5⋯𝑝±1	1982	Joe Buhler Richard E. Crandall M. A. Penk
+	Cours d'arithmétique	1995	Jean Pierre Serre
+	A Classical Introduction to Modern Number Theory	1982	Kenneth Ireland Michael Rosen
+	A primality test using cyclotomic extensions	1989	Preda Mihăilescu