Links 


 [LL03] 
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 48, 2003. Proceedings, volume
2656 of Lecture Notes in Computer Science, pages 360373. Springer Berlin
/ Heidelberg, May 2003.
Let p be a small prime and q=p^{n}. Let E be an
elliptic curve over GF(q). We propose an algorithm which
computes without any preprocessing the jinvariant 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 nbit 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^{2}) space
complexities. From a practical viewpoint, the corresponding
algorithm is particularly well suited for
implementations. We outline this by a 100002bit
computation.
[ bib 
preprint 
publication ]
Back 

