Hendrik Hubrechts

Memory efficient hyperelliptic curve point counting, pdf, 15 pages, version of 3 September 2009.
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. In this note 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.

The distribution of the number of points modulo an integer on elliptic curves over finite fields, with Wouter Castryck , pdf, 23 pages, version of 19 March 2009.
Abstract: Let F be a finite field of size q and let b and N be integers. We study the probability that the number of points on a randomly chosen elliptic curve E over F equals b modulo N. We prove explicit formulas for the cases gcd(N, q) = 1 and N = char(F). In the former case, these formulas follow from a random matrix theorem for Frobenius acting on the N-torsion part of E, obtained by applying density results due to Chebotarev to the modular covering X(N) -> X(1). As an additional application to this theorem, we estimate the probability that a randomly chosen elliptic curve has a point of order precisely N.

Point counting in families of hyperelliptic curves, pdf, 34 pages, version of 30 March 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, LMS J. Comput. Math. 10 (2007) 207--234, downloadable from LMS JCM. (earlier preprint, pdf, 27 pages, version of 8 May 2007)
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 March 2008. Accepted for the conference MEGA 2007.
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 2 February 2008. Accepted for ANTS-VIII 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 December 2009. To appear in Finite Fields and their Applications.
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.

• 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.