Reynald Lercier

R. Lercier and D Lubicz. Counting Points on Elliptic Curves over Finite Fields of Small Characteristic in Quasi Quadratic Time. In E. Biham, editor, Advances in Cryptology - EUROCRPYT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003. Proceedings, volume 2656 of Lecture Notes in Computer Science, pages 360-373. Springer Berlin / Heidelberg, May 2003.

Let p be a small prime and q=pⁿ. Let E be an elliptic curve over GF(q). We propose an algorithm which computes without any preprocessing the j-invariant of the canonical lift of E with the cost of O(logn) times the cost needed to compute a power of the lift of the Frobenius. Let μ be a constant so that the product of two n-bit length integers can be carried out in O(n^μ) bit operations, this yields an algorithm to compute the number of points on elliptic curves which reaches, at the expense of a O(n^5/2) space complexity, a theoretical time complexity bound equal to O(n^{max(1.19, μ)+μ+1/2}logn). When the field has got a Gaussian Normal Basis of small type, we obtain furthermore an algorithm with O(log(n)n^2μ) time and O(n²) space complexities. From a practical viewpoint, the corresponding algorithm is particularly well suited for implementations. We outline this by a 100002-bit computation.

[ bib | preprint | publication ] Back