On Elkies subgroups of -torsion points in elliptic curves defined over a finite field
Journal de Théorie des Nombres de Bordeaux, Tome 20 (2008) no. 3, pp. 783-797.

En sous-résultat de l’algorithme de Schoof-Elkies-Atkin pour compter le nombre de points d’une courbe elliptique définie sur un corps fini de caractéristique p, il existe un algorithme qui, pour un nombre premier d’Elkies, calcule des points de -torsion dans une extension de degré -1 à l’aide de O ˜(max(,logq) 2 ) opérations élémentaires à condition que p/2.

Nous combinons ici un algorithme rapide dû à Bostan, Morain, Salvy et Schost avec l’approche p-adique suivie par Joux et Lercier pour obtenir un algorithme valide sans limitation sur et p et de complexité similaire. Par soucis de simplification, nous décrivons précisément ici l’algorithme dans le cas des corps finis de caractéristique p5. Nous l’illustrons aussi avec quelques expérimentations.

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(,logq) 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 p5. We give experiment results too.

@article{JTNB_2008__20_3_783_0,
     author = {Lercier, Reynald and Sirvent, Thomas},
     title = {On Elkies subgroups of $\ell $-torsion points in elliptic curves defined over a finite field},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {783--797},
     publisher = {Universit\'e Bordeaux 1},
     volume = {20},
     number = {3},
     year = {2008},
     doi = {10.5802/jtnb.650},
     mrnumber = {2523317},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/jtnb.650/}
}
Lercier, Reynald; 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, Tome 20 (2008) no. 3, pp. 783-797. doi : 10.5802/jtnb.650. http://archive.numdam.org/articles/10.5802/jtnb.650/

[1] E.R. Berlekamp, Algebraic Coding Theory. McGraw-Hill, 1968. | MR 238597 | Zbl 0988.94521

[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. | MR 2398793

[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. | MR 604867 | Zbl 0475.65018

[4] H. Cohen On the coefficients of the transformation polynomials for the elliptic modular function. Math. Proc. Cambridge Philos. Soc. 95 (1984), 389–402. | MR 755826 | Zbl 0541.10026

[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. | MR 1446498 | Zbl 0903.11030

[6] J.-M. Couveignes, R. Lercier, Elliptic periods for finite fields. arXiv:0802.0165, 2008. To appear in Finite Fields and their Applications. | MR 2468989

[7] J.-M. Couveignes, R. Lercier, Galois invariant smoothness basis. Series on number theory and its application 5 (2008), 154–179. | MR 2484053 | Zbl 1151.14311

[8] J.-L. Dornstetter, On the equivalence between Berlekamp’s and Euclid’s algorithms. IEEE Transactions on Information Theory 33(3) (1987), 428–431. | MR 885401 | Zbl 0633.94019

[9] A. Enge, Computing modular polynomials in quasi-linear time. arXiv:0704.3177, 2007. To appear in Mathematics of Computation.

[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. | MR 1975526 | Zbl 1055.94013

[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. | MR 1446512 | Zbl 0911.11029

[13] R. Lidl, H. Niederreiter, Finite Fields, volume 20 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, 1983. | MR 746963 | Zbl 0554.12010

[14] J.L. Massey, Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory 15(1) (1969), 122–127. | MR 242556 | Zbl 0167.18101

[15] V.Y. Pan, New techniques for the computation of linear recurrence coefficients. Finite Fields and Their Applications 6(1) (2000), 93–118. | MR 1738216 | Zbl 0978.65130

[16] R. Schoof, Counting points on elliptic curves over finite fields. Journal de théorie des nombres de Bordeaux 7(1) (1995), 219–254. | Numdam | MR 1413578 | Zbl 0852.11073

[17] V. Shoup, Removing Randomness from Computational Number Theory. PhD thesis, University of Winsconsin, 1989.

[18] J.H. Silverman The arithmetic of elliptic curves, volume 106 of Graduate Texts in Mathematics. Springer-Verlag, 1986. Corrected reprint of the 1986 original. | MR 1329092 | Zbl 0585.14026

[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.

[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. | Zbl 0225.14014