Finding the group structure of elliptic curves over finite fields

John Friedlander, Carl Pomerance, Igor E. Shparlinski

Type: Article

Publication Date: 2005-10-01

Citations: 4

DOI: https://doi.org/10.1017/s0004972700035048

Abstract

We show that an algorithm of V. Miller to compute the group structure of an elliptic curve over a prime finite field runs in probabilistic polynomial time for almost all curves over the field. Important to our proof are estimates for some divisor sums.

Locations

Bulletin of the Australian Mathematical Society - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Group Structures of Elliptic Curves Over Finite Fields	2013	Vorrapan Chandee Chantal David Dimitris Koukoulopoulos Ethan Smith
+ PDF Chat	Finding elliptic curves with a subgroup of prescribed size	2016	Igor E. Shparlinski Andrew V. Sutherland
+ PDF Chat	Almost Primality of Group Orders of Elliptic Curves Defined over Small Finite Fields	2001	Neal Koblitz
+ PDF Chat	The Frequency of Elliptic Curve Groups over Prime Finite Fields	2015	Vorrapan Chandee Chantal David Dimitris Koukoulopoulos Ethan Smith
+	On group structures realized by elliptic curves over arbitrary finite fields	2010	William D. Banks Francesco Pappalardi Igor E. Shparlinski
+	On group structures realized by elliptic curves over arbitrary finite fields	2010	William D. Banks Francesco Pappalardi Igor E. Shparlinski
+ PDF Chat	On Group Structures Realized by Elliptic Curves over Arbitrary Finite Fields	2012	William D. Banks Francesco Pappalardi Igor E. Shparlinski
+	Constructing elliptic curves of prime order	2007	Reinier Bröker Peter Stevenhagen
+	Constructing elliptic curves of prime order	2008	Reinier Bröker Peter Stevenhagen
+	GROUP STRUCTURE OF ELLIPTIC CURVES OVER FINITE FIELDS AND APPLICATIONS	2006	Ram Murty Igor E. Shparlinski
+	Counting Prime Divisors on Elliptic Curves and Multiplication in Finite Fields	2000	Mohammad Amin Shokrollahi
+ PDF Chat	The distribution of group structures on elliptic curves over finite prime fields	2006	Ernst-Ulrich Gekeler
+	On the group orders of elliptic curves over finite fields	2001	Everett W. Howe
+	On the group orders of elliptic curves over finite fields	1993	Everett W. Howe
+ PDF Chat	On Group Structures Realized by Elliptic Curves over a Fixed Finite Field	2012	Reza Rezaeian Farashahi Igor E. Shparlinski
+	Elliptic and modular curves over finite fields and related computational issues	1997	Noam D. Elkies
+	Number theoretic algorithms for elliptic curves	2008	Lawrence C. Washington Juliana Belding
+	Finding points on curves over finite fields	2002	Joachim von zur Gathen Igor E. Shparlinski
+	Group structures of elliptic curves #1	2014	Igor E. Shparlinski
+	The Group Structure on an Elliptic Curve	2019	Nathan Alvarez Olson

Works That Cite This (3)

Action	Title	Year	Authors
+	Elliptic Curves over Finite Fields: Number Theoretic and Cryptographic Aspects	2012	Igor E. Shparlinski
+	GENERATORS OF ELLIPTIC CURVES OVER FINITE FIELDS	2011	Igor E. Shparlinski Jos E Felipe Voloch
+	GROUP STRUCTURE OF ELLIPTIC CURVES OVER FINITE FIELDS AND APPLICATIONS	2006	Ram Murty Igor E. Shparlinski

Works Cited by This (19)

Action	Title	Year	Authors
+ PDF Chat	The Arithmetic of Elliptic Curves	1986	Joseph H. Silverman
+	Multiplicative Number Theory	1980	H. Davenport
+ PDF Chat	Abelian varieties over finite fields	1969	William C. Waterhouse
+	The exponents of the groups of points on the reductions of an elliptic curve	1991	René Schoof
+ PDF Chat	The Weil Pairing, and Its Efficient Calculation	2004	Victor S. Miller
+ PDF Chat	Factoring Integers with Elliptic Curves	1987	H. W. Lenstra
+	Prime Numbers: A Computational Perspective	2012	Richard E. Crandall Carl Pomerance
+	How the Number of Points of An Elliptic Curve Over a Fixed Prime Field Varies	1968	B. J. Birch
+ PDF Chat	Elliptic curves over finite fields and the computation of square roots mod 𝑝	1985	René Schoof
+	Nonsingular plane cubic curves over finite fields	1987	René Schoof