Hendrik Hubrechts

The distribution of the number of points modulo an integer on elliptic curves over finite fields, with Wouter Castryck , pdf, 21 pages, version of 31/01/2011.
Abstract: Let F be a finite field and let b and N be integers. We prove explicit estimates for the probability that the number of rational points on a randomly chosen elliptic curve E over F equals b modulo N. The underlying tool is an equidistribution result on the action of Frobenius on the N-torsion subgroup of E. Our results subsume and extend previous work by Achter and Gekeler.

The probability that the number of points on the Jacobian of a genus 2 curve is prime, with Wouter Castryck, Amanda Folsom and Andrew Sutherland, pdf, 36 pages, version of 26/01/2011.
Abstract: In 2000, Galbraith and McKee heuristically derived a formula that estimates the probability that a randomly chosen elliptic curve over a fixed finite prime field has a prime number of rational points. We show how their heuristics can be generalized to Jacobians of curves of higher genus. We then elaborate this in genus g=2 and study various related issues, such as the probability of cyclicity and the probability of primality of the number of points on the curve itself. Finally, we discuss the asymptotic behavior for g going to infinity.

Point counting in families of hyperelliptic curves (pdf, 34 pages, version of 30/03/2007), Foundations of Computational Mathematics 8 (2008), no. 1, 137-169. Online.
Abstract: Let E_G be a family of hyperelliptic curves defined by Y ²=Q(X,G), where Q is defined over a small finite field of odd characteristic. Then with g in an extension degree n field over this small field, we present a deterministic algorithm for computing the zeta function of the curve E_g by using Dwork deformation in rigid cohomology. The time complexity of the algorithm is O(n^2.667) and it needs O(n^2.5) bits of memory. A slight adaptation requires only O(n²) space, but costs time O(n³). An implementation of this last result turns out to be quite efficient for n big enough.

Point counting in families of hyperelliptic curves in characteristic 2 (earlier preprint, pdf, 27 pages, version of 8/05/2007), LMS Journal of Computation and Mathematics 10 (2007) 207-234, downloadable from LMS JCM.
Abstract: Let E_G be a family of hyperelliptic curves over F₂^{alg cl} with general Weierstrass equation given over a very small field F. We describe in this paper an algorithm for computing the zeta function of E_g, with g in a degree n extension field of F, which has as time complexity O(n^3+epsilon) bit operations and memory requirements O(n²) bits. With a slightly different algorithm we can get time O(n^2.667) and memory O(n^2.5), and the computation for n curves of the family can be done in time O(n^3.376). All of these algorithms are polynomial-time in the genus.

Quasi-quadratic elliptic curve point counting using rigid cohomology (pdf, 17 pages, version of 26/03/2008), Journal of Symbolic Computation 44 (2009), no. 9, 1255-1267.
Abstract: We present a deterministic algorithm that computes the zeta function of a nonsupersingular elliptic curve E over a finite field with pⁿ elements in time quasi-quadratic in n. An older algorithm having the same time complexity uses the canonical lift of E, whereas our algorithm uses rigid cohomology combined with a deformation approach. An implementation in small odd characteristic turns out to give very good results.

Elliptic and hyperelliptic curve point counting through deformation (Ph.D. thesis), pdf, 173 pages, published at the K.U.Leuven.

Computing zeta functions in families of C_a,b curves using deformation, with Wouter Castryck and Frederik Vercauteren (pdf, 16 pages, version of 20/02/2008), Algorithmic number theory, 296-311, Lecture Notes in Computer Science, 5011, Springer, Berlin, 2008.
Abstract: We apply deformation theory to compute zeta functions in a family of C_a,b curves over a finite field of small characteristic. The method combines Denef and Vercauteren's extension of Kedlaya's algorithm to C_a,b curves with Hubrechts' recent work on point counting on hyperelliptic curves using deformation. As a result, it is now possible to generate C_a,b curves suitable for use in cryptography in a matter of minutes.

Fast arithmetic in unramified p-adic fields (pdf, 10 pages, version of 18/12/2009), Finite Fields and their Applications 16 (2010), issue 3, 155-162.
Abstract: Let p be prime and Z_pⁿ the degree n unramified extension of the ring of p-adic integers Z_p. In this paper we give an overview of some very fast deterministic algorithms for common operations in Z_pⁿ modulo p^N. Combining existing methods with recent work of Kedlaya and Umans about modular composition of polynomials, we achieve quasi-linear time algorithms in the parameters n and N, and quasi-linear or quasi-quadratic time in log(p), for most basic operations on these fields, including Galois conjugation, Teichmüller lifting and computing minimal polynomials.

Memory efficient hyperelliptic curve point counting (pdf, 13 pages, version of 29/03/2010), International Journal of Number Theory 7 (2011), issue 1, 203-214.
Abstract: In recent algorithms that use deformation in order to compute the number of points on varieties over a finite field, certain differential equations of matrices over p-adic fields emerge. We present a novel strategy to solve this kind of equations in a memory efficient way. The main application is an algorithm requiring quasi-cubic time and only quadratic memory in the parameter n, that solves the following problem: for E a hyperelliptic curve of genus g over a finite field of extension degree n and small characteristic, compute its zeta function. This improves substantially upon Kedlaya's result which has the same quasi-cubic time asymptotic, but requires also cubic memory size.

• Rennes, June 2006, Point counting in families of hyperelliptic curves
• Strobl, June 2007 (MEGA Conference), Quasi-quadratic elliptic curve point counting using rigid cohomology
• Hong Kong, June 2008 (Foundations of Computational Mathematics), Solving p-adic matrix differential equations
• Luminy (Marseille), March 2009, Point counting using deformation

• This program uses a new way to compute Frobenius from its differential equation, and is substantially faster in precomputations than the previous version (which can be found here).
  The files are supposed to be in a subfolder bigdeform of the Magma folder, and Magma has to be called from its own folder. You can use this program in two ways. The easiest way is to adapt the file testSeq.m to your needs, and simply type in load "bigdeform/testSeq.m" in Magma. The second way is to look at the beginning of FamHECSeq.m where the options are more or less explained.
  Download: Deformation.zip
  
• This program is essentially the same as the former, but it uses Harleys fast p-adic arithmetic as described by Vercauteren in 'Elliptic and Hyperelliptic Curve Cryptography'. It only works for the characteristics 3, 5 and 7, but it is a lot faster.
  The same remarks apply, but now with pathname bigdeform1.
  Download: DeformationFast.zip
  

• The file is pointcounting.m. After loading it the main interesting method is 'traceOfFrobenius()' which takes as argument an elliptic curve over a finite field. The verbose parameter 'User1' can be used to print intermediate timing results.