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

Lercier, Reynald; Sirvent, Thomas

doi:10.5802/jtnb.650

On Elkies subgroups of

ℓ

-torsion points in elliptic curves defined over a finite field

Lercier, Reynald ¹ ; Sirvent, Thomas ²

¹ DGA/CÉLAR La Roche Marguerite F-35174 Bruz
² IRMAR Université de Rennes 1 Campus de Beaulieu F-35042 Rennes

Journal de théorie des nombres de Bordeaux, Tome 20 (2008) no. 3, pp. 783-797.

Résumé
Abstract

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 $\tilde{O} (ℓ max {(ℓ, log q)}^{2})$ opérations élémentaires à condition que $ℓ \leq 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 $p \geq 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 $ℓ$ an Elkies prime, $ℓ$ -torsion points in an extension of degree $ℓ - 1$ at cost $\tilde{O} (ℓ max {(ℓ, log q)}^{2})$ bit operations in the favorable case where $ℓ \leq 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 \geq 5$ . We give experiment results too.

DOI : 10.5802/jtnb.650

Affiliations des auteurs :

Lercier, Reynald ¹ ; Sirvent, Thomas ²

¹ DGA/CÉLAR La Roche Marguerite F-35174 Bruz
² IRMAR Université de Rennes 1 Campus de Beaulieu F-35042 Rennes

@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 = {https://www.numdam.org/articles/10.5802/jtnb.650/}
}

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
SP  - 783
EP  - 797
VL  - 20
IS  - 3
PB  - Université Bordeaux 1
UR  - https://www.numdam.org/articles/10.5802/jtnb.650/
DO  - 10.5802/jtnb.650
LA  - en
ID  - JTNB_2008__20_3_783_0
ER  -

%0 Journal Article
%A Lercier, Reynald
%A Sirvent, Thomas
%T On Elkies subgroups of $\ell $-torsion points in elliptic curves defined over a finite field
%J Journal de théorie des nombres de Bordeaux
%D 2008
%P 783-797
%V 20
%N 3
%I Université Bordeaux 1
%U https://www.numdam.org/articles/10.5802/jtnb.650/
%R 10.5802/jtnb.650
%G en
%F JTNB_2008__20_3_783_0

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. https://www.numdam.org/articles/10.5802/jtnb.650/

Bibliographie
Cité par

[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 $(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 | 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

Cité par Sources :