On Elkies subgroups of ℓ -torsion points in elliptic curves defined over a finite field

Reynald Lercier[1]; Thomas Sirvent[2]

  • [1] DGA/CÉLAR La Roche Marguerite F-35174 Bruz
  • [2] IRMAR Université de Rennes 1 Campus de Beaulieu F-35042 Rennes

Journal de Théorie des Nombres de Bordeaux (2008)

  • Volume: 20, Issue: 3, page 783-797
  • ISSN: 1246-7405

Abstract

top
As a subproduct of the Schoof-Elkies-Atkin algorithm to count points on elliptic curves defined over finite fields of characteristic p , there exists an algorithm that computes, for ℓ an Elkies prime, ℓ -torsion points in an extension of degree ℓ - 1 at cost O ˜ ( ℓ max ( ℓ , log q ) 2 ) bit operations in the favorable case where ℓ ≤ p / 2 .We combine in this work a fast algorithm for computing isogenies due to Bostan, Morain, Salvy and Schost with the p -adic approach followed by Joux and Lercier to get an algorithm valid without any limitation on ℓ and p but of similar complexity. For the sake of simplicity, we precisely state here the algorithm in the case of finite fields with characteristic p ≥ 5 . We give experiment results too.

How to cite

top

Lercier, Reynald, and Sirvent, Thomas. "On Elkies subgroups of $\ell $-torsion points in elliptic curves defined over a finite field." Journal de Théorie des Nombres de Bordeaux 20.3 (2008): 783-797. <http://eudml.org/doc/10860>.

@article{Lercier2008,
abstract = {As a subproduct of the Schoof-Elkies-Atkin algorithm to count points on elliptic curves defined over finite fields of characteristic $p$, there exists an algorithm that computes, for $\ell $ an Elkies prime, $\ell $-torsion points in an extension of degree $\ell -1$ at cost $\mathop \{\{\tilde\{O\}\}\}\nolimits (\ell \, \max (\ell , \log q)^2)$ bit operations in the favorable case where $\ell \le p/2$.We combine in this work a fast algorithm for computing isogenies due to Bostan, Morain, Salvy and Schost with the $p$-adic approach followed by Joux and Lercier to get an algorithm valid without any limitation on $\ell $ and $p$ but of similar complexity. For the sake of simplicity, we precisely state here the algorithm in the case of finite fields with characteristic $p\ge 5$. We give experiment results too.},
affiliation = {DGA/CÉLAR La Roche Marguerite F-35174 Bruz; IRMAR Université de Rennes 1 Campus de Beaulieu F-35042 Rennes},
author = {Lercier, Reynald, Sirvent, Thomas},
journal = {Journal de Théorie des Nombres de Bordeaux},
language = {eng},
number = {3},
pages = {783-797},
publisher = {Université Bordeaux 1},
title = {On Elkies subgroups of $\ell $-torsion points in elliptic curves defined over a finite field},
url = {http://eudml.org/doc/10860},
volume = {20},
year = {2008},
}

TY - JOUR
AU - Lercier, Reynald
AU - Sirvent, Thomas
TI - On Elkies subgroups of $\ell $-torsion points in elliptic curves defined over a finite field
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2008
PB - Université Bordeaux 1
VL - 20
IS - 3
SP - 783
EP - 797
AB - As a subproduct of the Schoof-Elkies-Atkin algorithm to count points on elliptic curves defined over finite fields of characteristic $p$, there exists an algorithm that computes, for $\ell $ an Elkies prime, $\ell $-torsion points in an extension of degree $\ell -1$ at cost $\mathop {{\tilde{O}}}\nolimits (\ell \, \max (\ell , \log q)^2)$ bit operations in the favorable case where $\ell \le p/2$.We combine in this work a fast algorithm for computing isogenies due to Bostan, Morain, Salvy and Schost with the $p$-adic approach followed by Joux and Lercier to get an algorithm valid without any limitation on $\ell $ and $p$ but of similar complexity. For the sake of simplicity, we precisely state here the algorithm in the case of finite fields with characteristic $p\ge 5$. We give experiment results too.
LA - eng
UR - http://eudml.org/doc/10860
ER -

References

top
  1. E.R. Berlekamp, Algebraic Coding Theory. McGraw-Hill, 1968. Zbl0988.94521MR238597
  2. A. Bostan, F. Morain, B. Salvy, É. Schost, Fast algorithms for computing isogenies between elliptic curves. Mathematics of Computation 77(263) (July 2008), 1755–1778. Zbl1200.11097MR2398793
  3. R.P. Brent, F.G. Gustavson, D.Y.Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants. Journal of Algorithms 1 (1980), 259–295. Zbl0475.65018MR604867
  4. H. CohenOn the coefficients of the transformation polynomials for the elliptic modular function. Math. Proc. Cambridge Philos. Soc. 95 (1984), 389–402. Zbl0541.10026MR755826
  5. J.-M. Couveignes, Computing l -isogenies with the p -torsion. In Proc. of the 2nd Algorithmic Number Theory Symposium (ANTS-II), volume 1122, pages 59–65, 1996. Zbl0903.11030MR1446498
  6. J.-M. Couveignes, R. Lercier, Elliptic periods for finite fields. arXiv:0802.0165, 2008. To appear in Finite Fields and their Applications. Zbl1216.11106MR2468989
  7. J.-M. Couveignes, R. Lercier, Galois invariant smoothness basis. Series on number theory and its application 5 (2008), 154–179. Zbl1151.14311MR2484053
  8. J.-L. Dornstetter, On the equivalence between Berlekamp’s and Euclid’s algorithms. IEEE Transactions on Information Theory 33(3) (1987), 428–431. Zbl0633.94019MR885401
  9. A. Enge, Computing modular polynomials in quasi-linear time. arXiv:0704.3177, 2007. To appear in Mathematics of Computation. Zbl1215.11121
  10. S.D. Galbraith, F. Hess, N.P. Smart, Extending the GHS Weil Descent Attack. In Proc. of Advances in Cryptology – Eurocrypt’2002, volume 2332, pages 29–44, 2002. Zbl1055.94013MR1975526
  11. A. Joux, R. Lercier, Counting points on elliptic curves in medium characteristic. Cryptology ePrint Archive 2006/176, 2006. 
  12. R. Lercier, Computing isogenies in GF ( 2 n ) . In H. Cohen, editor, Algorithmic Number Theory: Second International Symposium, ANTS-II, volume 1122 of LNCS, pages 197–212. Springer Berlin / Heidelberg, May 1996. Zbl0911.11029MR1446512
  13. R. Lidl, H. Niederreiter, Finite Fields, volume 20 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, 1983. Zbl0554.12010MR746963
  14. J.L. Massey, Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory 15(1) (1969), 122–127. Zbl0167.18101MR242556
  15. V.Y. Pan, New techniques for the computation of linear recurrence coefficients. Finite Fields and Their Applications 6(1) (2000), 93–118. Zbl0978.65130MR1738216
  16. R. Schoof, Counting points on elliptic curves over finite fields. Journal de théorie des nombres de Bordeaux 7(1) (1995), 219–254. Zbl0852.11073MR1413578
  17. V. Shoup, Removing Randomness from Computational Number Theory. PhD thesis, University of Winsconsin, 1989. 
  18. J.H. SilvermanThe arithmetic of elliptic curves, volume 106 of Graduate Texts in Mathematics. Springer-Verlag, 1986. Corrected reprint of the 1986 original. Zbl0585.14026MR1329092
  19. N.P. Smart, An Analysis of Goubin’s Refined Power Analysis Attack. In Proc. of the 5th Workshop on Cryptographic Hardware and Embedded Systems (CHES’2003), volume 2779, pages 281–290, 2003. Zbl1274.94116
  20. J. Vélu, Isogénies entre courbes elliptiques. Comptes Rendus de l’Académie des Sciences de Paris 273 (1971), 238–241. Série A. Zbl0225.14014

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.