Bull. Austral. Math. Soc. 72(2) pp.251--263, 2005.
Finding the group structure of elliptic curves over finite fields
John B. Friedlander |
Carl Pomerance |
Igor E. Shparlinski |
During the preparation of this paper, the first author
was supported in part by NSERC grant A5123 and by a Killam Research
Fellowship.
The second author was supported in part by NSF grant DMS-0401422
and the third author was supported in part by ARC grant
DP0211459.
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.
Click to download PDF of this article (free access until July 2006)
or get the no-frills version
[an error occurred while processing this directive]| (Metadata: XML, RSS, BibTeX) | MathSciNet: MR2183406 | Z'blatt-MATH: 02246387 |
References
- M. Agrawal, N. Kayal and N. Saxena;
PRIMES is in P,
Ann. of Math. (2) 60 (2004), pp. 781--793. MR2123939 - R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen and
F. Vercauteren;
(to appear)Elliptic and hyperelliptic curve crytography: Theory and practice (CRC Press to appear). MR2162716 - B.J. Birch;
How the number of points of an elliptic curve over a fixed prime field varies,
J. Lond. Math. Soc. 43 (1968), pp. 57--60. MR230682 - I. Blake, G. Seroussi and N. Smart;
Elliptic curves in cryptography,
London Math. Soc. Lecture Note Series 265 (Cambridge Univ. Press, Cambridge, 1999). MR1771549 - D. Coppersmith;
Modifications to the number field sieve,
J. Cryptology 6 (1993), pp. 169--180. MR1233462 - R. Crandall and C. Pomerance;
Prime numbers: A computational perspective (Springer-Verlag, Berlin, 2001). MR1821158 - H. Davenport;
Multiplicative number theory,
2nd edition (Springer-Verlag, New York, 1980). MR606931 - M. Deuring;
Die Typen der Multiplikatorenringe elliptischer Funktionenk{ö}rper,
Abh. Math. Sem. Hansischen Univ. 14 (1941), pp. 197--272. MR5125 - D.R. Kohel and I.E. Shparlinski;
Exponential sums and group generators for elliptic curves over finite fields,
Lect. Notes in Comp. Sci. 1838 (Springer-Verlag, Berlin, 2000), pp. 395--404. MR1850620 - H.W. Lenstra, Jr.;
Factoring integers with elliptic curves,
Annals of Math. 126 (1987), pp. 649--673. MR916721 - H.W. Lenstra, Jr., J. Pila and C. Pomerance;
A hyperelliptic smoothness test, I,
Philos. Trans. Royal Soc. London, Ser. A. 345 (1993), pp. 397--408. MR1253501 - H.W. Lenstra, Jr. and C. Pomerance;
A rigorous time bound for factoring integers,
J. Amer. Math. Soc. 5 (1992), pp. 483--516. MR1137100 - H.W. Lenstra, Jr. and C. Pomerance;
Primality testing with Gaussian periods,
(in preparation). - F. Luca, J. McKee and I.E. Shparlinski;
Small exponent point groups on elliptic curves,
J. Th{é}or. Nombres Bordeaux (to appear). - F. Luca and I.E. Shparlinski;
On the exponent of the group of points on elliptic curves in extension fields,
Internat. Math. Res, Notices (to appear). MR2152235 - V.S. Miller;
The Weil pairing, and its efficient calculation,
J. Cryptology 17 (2004), pp. 235--261. MR2090556 - C. Pomerance;
Analysis and comparison of some integer factoring algorithms,
in Computational Methods in Number Theory, Part I,
(H.W. Lenstra, Jr. and R. Tijdeman, Editors),
Math. Centre Tracts 154 (Math Centrum, Amsterdam, 1982), pp. 89--139. MR700260 - K. Prachar;
Primzahlverteilung (Springer-Verlag, Berlin, 1957). MR87685 - R. Schoof;
Elliptic curves over finite fields and the computation of square roots mod p,
Math. Comp. 44 (1985), pp. 483--494. MR777280 - R. Schoof;
Nonsingular plane cubic curves over finite fields,
J. Combin. Theory, Ser.A 47 (1987), pp. 183--211. MR914657 - R. Schoof;
The exponents of the group of points on the reduction of an elliptic curve,
in Arithmetic Algebraic Geometry,
Progr. Math. 89 (Birkhäuser, Boston, MA, 1991), pp. 325--335. MR1085266 - J.H. Silverman;
The arithmetic of elliptic curves (Springer-Verlag, Berlin, 1995). MR817210 - W.C. Waterhouse;
Abelian varieties over finite fields,
Ann. Sci. Ecole Norm. Sup. 2 (1969), pp. 521--560. MR265369
ISSN 0004-9727