Reinier Bröker

We study the problem of efficiently constructing a curve C of genus 2 over a finite field F for which either the curve C itself or its Jacobian has a prescribed number N of F-rational points. In the case of the Jacobian, we show that any `CM-construction' to produce the required genus-2 curves necessarily takes time exponential in the size of its input. On the other hand, we provide an algorithm for producing a genus-2 curve with a given number of points that, heuristically, takes polynomial time for most input values. We illustrate the practical applicability of this algorithm by constructing a genus-2 curve having exactly 10^2014 + 9703 (prime) points, and two genus-2 curves each having exactly 10^2013 points. In an appendix we provide a complete parametrization, over an arbitrary base field k of characteristic neither 2 nor 3, of the family of genus-2 curves over k that have k-rational degree-3 maps to elliptic curves, including formulas for the genus-2 curves, the associated elliptic curves, and the degree-3 maps.

The moduli space of principally polarized abelian surfaces is parametrized by three Igusa functions. In this article we investigate a new way to evaluate these functions by using the Siegel Eisenstein series. We explain how to compute the Fourier coefficients of certain Siegel modular forms using classical modular forms of half-integral weight. One of the results in this paper is an explicit algorithm to evaluate the Igusa functions to a prescribed precision.

We present a new algorithm to compute the classical modular polynomial Phi_n in the rings Z[X,Y] and (Z/mZ)[X,Y], for a prime n and any positive integer m. Our approach uses the graph of n-isogenies to efficiently compute Phi_n mod p for many primes p of a suitable form, and then applies the Chinese Remainder Theorem (CRT). Under the Generalized Riemann Hypothesis (GRH), we achieve an expected running time of O(n^3 (log n)^3 log log n), and compute Phi_n mod m using O(n^2 (log n)^2 + n^2 log m) space. We have used the new algorithm to compute Phi_n with n over 5000, and Phi_n mod m with n over 20000. We also consider several modular functions g for which Phi_n^g is smaller than Phi_n, allowing us to handle n over 60000.

We present a new algorithm to compute the classical modular polynomial Φ l \Phi _l in the rings Z [ X , Y ] \mathbf {Z}[X,Y] and ( Z / m Z ) [ X , Y ] (\mathbf {Z}/m\mathbf {Z})[X,Y] , for a prime l l and any positive integer m m . Our approach uses the graph of l l -isogenies to efficiently compute Φ l mod p \Phi _l\bmod p for many primes p p of a suitable form, and then applies the Chinese Remainder Theorem (CRT). Under the Generalized Riemann Hypothesis (GRH), we achieve an expected running time of O ( l 3 ( log ⁡ l ) 3 log ⁡ log ⁡ l ) O(l^3 (\log l)^3\log \log l) , and compute Φ l mod m \Phi _l\bmod m using O ( l 2 ( log ⁡ l ) 2 + l 2 log ⁡ m ) O(l^2(\log l)^2+ l^2\log m) space. We have used the new algorithm to compute Φ l \Phi _l with l l over 5000, and Φ l mod m \Phi _l\bmod m with l l over 20000. We also consider several modular functions g g for which Φ l g \Phi _l^g is smaller than Φ l \Phi _l , allowing us to handle l l over 60000.

We develop a newp-adic algorithm to compute the minimal polynomial of a class invariant. Our approach works for virtually any modular function yielding class invariants. The main algorithmic tool is modular polynomials, a concept which we generalize to functions of higher level.

The moduli space of principally polarized abelian surfaces is parametrized by three Igusa functions. In this article we investigate a new way to evaluate these functions by using Siegel Eisenstein series. We explain how to compute the Fourier coefficients of certain Siegel modular forms using classical modular forms of half-integral weight. One of the results in this paper is an explicit algorithm to evaluate the Igusa functions to a prescribed precision.