staple
Avec cedram.org

Rechercher dans le site

Table des matières de ce fascicule | Article précédent | Article suivant
Reynald Lercier; Thomas Sirvent
On Elkies subgroups of $\ell $-torsion points in elliptic curves defined over a finite field
Journal de théorie des nombres de Bordeaux, 20 no. 3 (2008), p. 783-797, doi: 10.5802/jtnb.650
Article PDF | Analyses MR 2523317 | Zbl pre05572701

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 $\ell $ un nombre premier d’Elkies, calcule des points de $\ell $-torsion dans une extension de degré $\ell -1$ à l’aide de $\mathop {{\tilde{O}}}\nolimits (\ell \, \max (\ell , \log q)^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.

Bibliographie

[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. arXiv |  MR 2468989 |  Zbl pre05488563
[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. Cedram |  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