zbMATH — the first resource for mathematics

On Elkies subgroups of \(\ell\)-torsion points in elliptic curves defined over a finite field. (English) Zbl 1230.11080
Summary: 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,\log q)^2)\) bit operations in the favorable case where \(\ell\leq p/2\).
We combine in this work a fast algorithm for computing isogenies due to A. Bostan, F. Morain, B. Salvy and É. Schost [Math. Comput. 77, No. 263, 1755–1778 (2008; Zbl 1200.11097)] 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\geq 5\). We give experiment results, too.

11G20 Curves over finite and local fields
11Y16 Number-theoretic algorithms; complexity
Full Text: DOI Numdam EuDML arXiv
[1] E.R. Berlekamp, Algebraic Coding Theory. McGraw-Hill, 1968. · 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. · Zbl 1200.11097
[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 0475.65018
[4] H. CohenOn the coefficients of the transformation polynomials for the elliptic modular function. Math. Proc. Cambridge Philos. Soc. 95 (1984), 389-402. · 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. · 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. · Zbl 1216.11106
[7] J.-M. Couveignes, R. Lercier, Galois invariant smoothness basis. Series on number theory and its application 5 (2008), 154-179. · 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. · Zbl 0633.94019
[9] A. Enge, Computing modular polynomials in quasi-linear time. arXiv:0704.3177, 2007. To appear in Mathematics of Computation. · Zbl 1215.11121
[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 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. · Zbl 0911.11029
[13] R. Lidl, H. Niederreiter, Finite Fields, volume 20 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, 1983. · Zbl 0554.12010
[14] J.L. Massey, Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory 15(1) (1969), 122-127. · 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. · 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. · Zbl 0852.11073
[17] V. Shoup, Removing Randomness from Computational Number Theory. PhD thesis, University of Winsconsin, 1989.
[18] J.H. SilvermanThe arithmetic of elliptic curves, volume 106 of Graduate Texts in Mathematics. Springer-Verlag, 1986. Corrected reprint of the 1986 original. · 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. · Zbl 1274.94116
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.