On Elkies subgroups of $\ell$-torsion points in elliptic curves defined over a finite field

Lercier, Reynald; Sirvent, Thomas

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 $\ell$ un nombre premier d’Elkies, calcule des points de $\ell$-torsion dans une extension de degré $\ell -1$ à l’aide de $\tilde{O}(\ell max{(\ell ,logq)}^2)$ opérations élémentaires à condition que $\ell \le 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 $\ell$ 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 $p\ge 5$. 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 $\ell$ an Elkies prime, $\ell$-torsion points in an extension of degree $\ell -1$ at cost $\tilde{O}(\ell max{(\ell ,logq)}^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.

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

[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

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

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

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

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

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

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

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

[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$\left(2^n\right)$. 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 | Zbl

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

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

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

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

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

[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