As a subproduct of the Schoof-Elkies-Atkin algorithm to count points on elliptic curves defined over finite fields of characteristic , there exists an algorithm that computes, for an Elkies prime, -torsion points in an extension of degree at cost bit operations in the favorable case where .
We combine in this work a fast algorithm for computing isogenies due to Bostan, Morain, Salvy and Schost with the -adic approach followed by Joux and Lercier to get an algorithm valid without any limitation on and but of similar complexity. For the sake of simplicity, we precisely state here the algorithm in the case of finite fields with characteristic . We give experiment results too.
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 , il existe un algorithme qui, pour un nombre premier d’Elkies, calcule des points de -torsion dans une extension de degré à l’aide de opérations élémentaires à condition que .
Nous combinons ici un algorithme rapide dû à Bostan, Morain, Salvy et Schost avec l’approche -adique suivie par Joux et Lercier pour obtenir un algorithme valide sans limitation sur et 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 . Nous l’illustrons aussi avec quelques expérimentations.
@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},
year = {2008},
publisher = {Universit\'e Bordeaux 1},
volume = {20},
number = {3},
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
[1] E.R. Berlekamp, Algebraic Coding Theory. McGraw-Hill, 1968. | Zbl | MR
[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. | Zbl | MR
[4] H. Cohen On the coefficients of the transformation polynomials for the elliptic modular function. Math. Proc. Cambridge Philos. Soc. 95 (1984), 389–402. | Zbl | MR
[5] J.-M. Couveignes, Computing -isogenies with the -torsion. In Proc. of the 2nd Algorithmic Number Theory Symposium (ANTS-II), volume 1122, pages 59–65, 1996. | Zbl | MR
[6] J.-M. Couveignes, R. Lercier, Elliptic periods for finite fields. | arXiv | MR
[7] J.-M. Couveignes, R. Lercier, Galois invariant smoothness basis. Series on number theory and its application 5 (2008), 154–179. | Zbl | MR
[8] J.-L. Dornstetter, On the equivalence between Berlekamp’s and Euclid’s algorithms. IEEE Transactions on Information Theory 33(3) (1987), 428–431. | Zbl | MR
[9] A. Enge, Computing modular polynomials in quasi-linear time. | arXiv
[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. | Zbl | MR
[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. In H. Cohen, editor, Algorithmic Number Theory: Second International Symposium, ANTS-II, volume 1122 of LNCS, pages 197–212. Springer Berlin / Heidelberg, May 1996. | Zbl | MR
[13] R. Lidl, H. Niederreiter, Finite Fields, volume 20 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, 1983. | Zbl | MR
[14] J.L. Massey, Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory 15(1) (1969), 122–127. | Zbl | MR
[15] V.Y. Pan, New techniques for the computation of linear recurrence coefficients. Finite Fields and Their Applications 6(1) (2000), 93–118. | Zbl | MR
[16] R. Schoof, Counting points on elliptic curves over finite fields. Journal de théorie des nombres de Bordeaux 7(1) (1995), 219–254. | Zbl | MR | Numdam
[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. | Zbl | MR
[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 :
