More Web Proxy on the site http://driver.im/

Article

Computing the eigenvalue in the schoof-elkies-atkin algorithm using abelian lifts

Authors:

É. SchostAuthors Info & Claims

ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

Pages 285 - 292

https://doi.org/10.1145/1277548.1277587

Published: 29 July 2007 Publication History

Abstract

The Schoof-Elkies-Atkin algorithm is the best known method for counting the number of points of an elliptic curve defined over a finite field of large characteristic. We use Abelian properties of division polynomials to design a fast theoretical and practical algorithm for nding the eigenvalue.

References

[1]

A.O.L. Atkin. The number of points on an elliptic curve modulo a prime (II). Available at http://listserv.nodak.edu/archives/nmbrthry.html July 1992.

[2]

I. Blake, G. Seroussi, and N. Smart. Elliptic curves in cryptography volume 265 of London Math. Soc. Lecture Note Ser. Cambridge University Press, 1999.

Digital Library

[3]

A. Bostan, F. Morain, B. Salvy, and É. Schost. Fast algorithms for computing isogenies between elliptic curves, 2006.

[4]

R.P. Brent and H.T. Kung. Fast algorithms for manipulating formal power series. J. ACM 25(4):581--595, 1978.

Digital Library

[5]

D.G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica 28(7):693--701, 1991.

Digital Library

[6]

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3):251--280, 1990.

Digital Library

[7]

J.-M. Couveignes, L. Dewaghe, and F. Morain. Isogeny cycles and the Schoof-Elkies-Atkin algorithm. Research Report LIX/RR/96/03, LIX, Apr. 1996. Available at http://www.lix.polytechnique.fr/Labo/Francois.Morain/

[8]

J.-M. Couveignes and F. Morain. Schoof's algorithm and isogeny cycles. In L. Adleman and M.-D. Huang, editors, Algorithmic Number Theory volume 877 of Lecture Notes in Comput. Sci. pages 43--58. Springer-Verlag, 1994. 1st Algorithmic Number Theory Symposium-Cornell University, May 6-9, 1994.

Digital Library

[9]

L. Dewaghe. Calcul du nombre de points sur une courbe elliptique dans un corps fini Thèse, Université des Sciences et Technologies de Lille, Dec. 1996.

[10]

L. Dewaghe. Remarks on the Schoof-Elkies-Atkin algorithm. Math. Comp.67(223):1247--1252, July 1998.

Digital Library

[11]

N.D. Elkies. Explicit isogenies. Draft, 1992.

[12]

N.D. Elkies. Elliptic and modular curves over finite fields and related computational issues. In Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin volume 7 of AMS/IP Studies in Advanced Mathematics pages 21--76. AMS, International Press, 1998.

[13]

A. Enge. Computing modular polynomials in quasi-linear time, 2006.

[14]

J. von zur Gathen and J. Gerhard. Modern Computer Algebra Cambridge University Press, 1999.

Digital Library

[15]

J. von zur Gathen and V. Shoup. Computing Frobenius maps and factoring polynomials. Comput. Complexity 2(3):187--224, 1992.

[16]

P. Gaudry and F. Morain. Fast algorithms for computing the eigenvalue in the Schoof-Elkies-Atkin algorithm. In ISSAC'06 pages 109--115. ACM Press, 2006.

Digital Library

[17]

E. Kaltofen and V. Shoup. Subquadratic-time factoring of polynomials over finite fields. Math. Comput. 67(223):1179--1197, 1998.

Digital Library

[18]

H.W.J. Lenstra. Galois theory and primality testing. In Orders and their applications volume 1142 of Lecture Notes in Mathematics pages 1--21. Springer Verlag, 1985.

[19]

M. Maurer and V. Müller. Finding the eigenvalue in Elkies' algorithm. Experiment. Math. 10(2):275--285, 2001.

[20]

P. Mihailescu. Cyclotomy primality proofs and their certificates. Mathematica Goettingensis, 2006.

[21]

P. Mihailescu. Elliptic curve Gauss sums and counting points. Mathematica Goettingensis, 2006.

[22]

F. Morain. Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques. J. Théor. Nombres Bordeaux 7:255--282, 1995.

[23]

C. Pascal and É. Schost.Change of order for bivariate triangular sets. In ISSAC'06 pages 277--284. ACM Press, 2006.

Digital Library

[24]

F. Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. Appl. Alg. in Eng. Comm. Comput. 9(5):433--461, 1999.

[25]

A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing 7:281--292, 1971.

[26]

R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p Math. Comp. 44(170):483--494, 1985.

[27]

R. Schoof. Counting points on elliptic curves over finite fields. J. Théor. Nombres Bordeaux 7:219--254, 1995.

[28]

J.-P. Serre. Propriétés galoisiennes des points d'ordre ni des courbes elliptiques. Invent. Math. 15(4):259--331, 1971.

[29]

V. Shoup. Fast construction of irreducible polynomials over finite fields. J. Symbolic Comput. 17:371--391, 1994.

Digital Library

[30]

V. Shoup. A new polynomial factorization algorithm and its implementation. J. Symbolic Comput. 20:363--397, 1995.

Digital Library

[31]

V. Shoup. Efficient computation of minimal polynomials in algebraic extensions of finite fields. In ISSAC'99 pages 53--58. ACM Press, 1999.

Digital Library

Cited By

Wong S(2022)Abelian lifts of polynomialsJournal of Number Theory10.1016/j.jnt.2022.09.008Online publication date: Oct-2022
https://doi.org/10.1016/j.jnt.2022.09.008
Poteaux ASchost É(2018)Modular Composition Modulo Triangular Sets and ApplicationsComputational Complexity10.1007/s00037-013-0063-y22:3(463-516)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00037-013-0063-y
Morain FScribot CSmith B(2016)Computing cardinalities of -curve reductions over finite fieldsLMS Journal of Computation and Mathematics10.1112/S146115701600026719:A(115-129)Online publication date: 26-Aug-2016
https://doi.org/10.1112/S1461157016000267
Show More Cited By

Index Terms

Computing the eigenvalue in the schoof-elkies-atkin algorithm using abelian lifts
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Number-theoretic computations

Recommendations

Fast algorithms for computing the eigenvalue in the Schoof-Elkies-Atkin algorithm
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

The Schoof-Elkies-Atkin algorithm is the best known algorithm for counting the number of points of an elliptic curve defined over a finite field of large characteristic. Several practical and asymptotical improvements for the phase called eigenvalue ...
On the Distribution of Atkin and Elkies Primes

Given an elliptic curve $$E$$E over a finite field $$\mathbb {F}_q$$Fq of $$q$$q elements, we say that an odd prime $$\ell \not \mid q$$ýýq is an Elkies prime for $$E$$E if $$t_E^2 - 4q$$tE2-4q is a square modulo $$\ell $$ý, where $$t_E = q+1 - \#E(\...
Elliptic near-MDS codes over $${\mathbb{F}}_5$$

Let ý 6 be the elliptic curve of degree 6 in PG (5, q ) arising from a non-singular cubic curve $${\mathcal{E}}$$ of PG (2, q ) via the canonical Veronese embedding $$\nu:\quad (X,Y,Z)\to (X^2,XY,Y^2,XZ,YZ,Z^2).$$ (1) If ý 6 (equivalently $${\mathcal{E}}...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

July 2007

406 pages

ISBN:9781595937438

DOI:10.1145/1277548

General Chair:
Dongming Wang
Beihang University and UPMC-CNRS (China/France)

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC07

Sponsor:

ISSAC07: International Symposium on Symbolic and Algebraic Computation

July 29 - August 1, 2007

Ontario, Waterloo, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
153
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wong S(2022)Abelian lifts of polynomialsJournal of Number Theory10.1016/j.jnt.2022.09.008Online publication date: Oct-2022
https://doi.org/10.1016/j.jnt.2022.09.008
Poteaux ASchost É(2018)Modular Composition Modulo Triangular Sets and ApplicationsComputational Complexity10.1007/s00037-013-0063-y22:3(463-516)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00037-013-0063-y
Morain FScribot CSmith B(2016)Computing cardinalities of -curve reductions over finite fieldsLMS Journal of Computation and Mathematics10.1112/S146115701600026719:A(115-129)Online publication date: 26-Aug-2016
https://doi.org/10.1112/S1461157016000267
Mihăilescu PRassias M(2014)Computational Number Theory and CryptographyApplications of Mathematics and Informatics in Science and Engineering10.1007/978-3-319-04720-1_22(349-373)Online publication date: 29-Mar-2014
https://doi.org/10.1007/978-3-319-04720-1_22
Mullen GPanario D(2013)BibliographyHandbook of Finite Fields10.1201/b15006-22(851-1010)Online publication date: 18-Jun-2013
https://doi.org/10.1201/b15006-22

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents