🔢 mathematics

Computing class groups and gonalities of algebraic curves over finite fields

This paper presents practical algorithms that significantly accelerate the computation of divisor class groups and gonalities for algebraic curves over finite fields by utilizing a precomputation step involving power series expansions to efficiently amortize the calculation of large numbers of Riemann-Roch spaces.

Original authors: Maarten Derickx, Kenji Terao

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Maarten Derickx, Kenji Terao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a mathematician trying to solve a massive puzzle involving shapes called algebraic curves that exist over finite fields (think of these as mathematical universes with a limited number of points, like a grid with only 5 or 100 dots instead of an infinite line).

The authors, Maarten Derickx and Kenji Terao, have built a new, super-fast engine to solve two specific types of puzzles about these curves:

The Class Group: A way to categorize and count the different "shapes" or arrangements of points on the curve.
The Gonality: A measure of how "twisted" or complex the curve is (specifically, how hard it is to flatten the curve onto a simple line).

Here is how their new method works, explained through everyday analogies.

The Old Way: The "Do-It-Yourself" Approach

Previously, to solve these puzzles, mathematicians had to check millions of different arrangements of points one by one.

The Bottleneck: For every single arrangement, they had to perform a very heavy, complex calculation (called finding a "Riemann-Roch space"). It was like trying to bake a million different cakes, but for every single cake, you had to grow your own wheat, mill the flour, and churn the butter from scratch before you could even start mixing the batter.
The Result: This took hours, days, or even weeks. If the curve was large or the field was big, the computer would often give up and crash because the task was too heavy.

The New Way: The "Pre-Prepared Kitchen"

The authors' breakthrough is a precomputation step. Instead of starting from scratch for every single calculation, they set up a massive "kitchen" once, and then use it to whip up thousands of results instantly.

1. The Master Recipe (Precomputation)

First, they pick one huge, complex arrangement of points (a "large divisor"). They do the heavy lifting once to create a detailed "master recipe" (a power series expansion) for this specific arrangement.

Analogy: Imagine you are a chef. Instead of grinding flour for every cake, you grind a giant mountain of flour once at the start of the day. You also prepare a giant batch of pre-mixed batter.

2. The Assembly Line (Linear Algebra)

Once that heavy prep work is done, calculating the result for any new arrangement of points becomes incredibly easy.

The Trick: They realized that finding the answer for a new arrangement is just a matter of doing simple math (linear algebra) on the pre-prepared data.
Analogy: Now, instead of growing wheat for every cake, you just grab a scoop of your pre-ground flour and a cup of your pre-mixed batter. You just have to mix them in a specific bowl. This takes seconds instead of hours.
The Speedup: Because the "mixing" is so fast, they can check millions of arrangements in the time it used to take to check a few dozen. The paper claims this makes the process hundreds of times faster (orders of magnitude) for large, complex curves.

Two Specific Puzzles They Solved

1. Measuring the "Twist" (Gonality)
To find out how twisted a curve is, you have to check if you can draw a line through it in a certain way.

Old Way: Check every possible line, do the heavy "grow-wheat" calculation for each.
New Way: Do the "grow-wheat" calculation once. Then, check millions of lines using the "scoop-and-mix" method.
Result: They can now solve these puzzles for curves that were previously impossible to handle, allowing them to study millions of modular curves (a specific type of curve used in number theory) much faster.

2. Counting the Shapes (Class Groups)
To understand the group of shapes on the curve, they need to find relationships between different point arrangements.

Old Way: Generate random arrangements, do the heavy calculation, and see if they fit.
New Way: Use the pre-computed "master recipe" to quickly test millions of random arrangements.
Result: They can find the necessary relationships much faster, though they note that one part of the process (checking if a shape is "smooth") still requires some heavy lifting, so the speedup here is good but not quite as massive as with the gonality.

The Bottom Line

The paper doesn't just offer a theory; they wrote actual computer code (available on GitHub) that proves this works.

Real-world impact: They tested their code on a server and found that tasks that used to take hundreds of hours (or even weeks) now take minutes or hours.
Why it matters: This allows mathematicians to tackle problems that were previously "too hard to compute," opening the door to new discoveries in number theory that were stuck waiting for a faster computer.

In short: They stopped reinventing the wheel for every single problem and instead built a factory that mass-produces the wheels, making the whole process incredibly efficient.

Technical Summary: Computing Class Groups and Gonalities of Algebraic Curves over Finite Fields

1. Problem Statement

The paper addresses the computational challenge of determining two fundamental invariants of algebraic curves over finite fields: the divisor class group (isomorphic to the Picard group in the authors' setting) and the gonality (the minimal degree of a non-constant map to the projective line).

Explicit computation of these invariants is critical for various applications in number theory, including the study of rational points on curves via the Mordell-Weil sieve, the analysis of torsion subgroups of Jacobians, and the investigation of points on modular curves. However, existing methods face severe performance bottlenecks, particularly for curves of large genus or over large residue fields. The primary limitation is the requirement to compute Riemann-Roch spaces for thousands or millions of divisors. Standard algorithms, such as those by Hess, rely on ideal and polynomial arithmetic which, while efficient for single computations, become infeasible when scaled to the millions of operations required for these invariants.

2. Methodology

The authors propose a new approach that shifts the computational burden from repeated polynomial arithmetic to efficient linear algebra. The core methodology relies on a precomputation step involving power series expansions, which allows for the amortized computation of large numbers of Riemann-Roch spaces.

2.1. Precomputation via Series Expansions

Instead of computing each Riemann-Roch space $L(D)$ independently, the algorithm fixes a large divisor $D_0$ and precomputes the Riemann-Roch space $L(D_0)$ along with series expansions for its basis functions.

Theoretical Basis: Theorem 3.1 establishes that for a fixed basis of $L(D_0)$ , the subspace $L(D_0 - D)$ (where $D$ is an effective divisor) can be identified with the nullspace of a specific matrix $A$ . The entries of $A$ are derived from the coefficients of the series expansions of the basis functions at the points supporting $D$ .
Efficiency: Once the vectors defining matrix $A$ are precomputed, determining the dimension of $L(D_0 - D)$ reduces to a rank computation of a matrix over a finite field, which is significantly faster than polynomial arithmetic.

2.2. Optimizations for Series Expansion

To ensure the precomputation step is practical, the authors introduce three specific improvements over existing Magma intrinsics:

Uniformizing Parameters (Algorithm 3.2): Instead of using standard algorithms that often yield high-degree polynomials, the authors compute uniformizers as low-degree polynomials in coordinate functions. This avoids expensive polynomial divisions.
Avoiding Hensel Lifting: The algorithm avoids computing the subring $k(x) \subset \hat{O}_{X,x}$ via Hensel lifting. Instead, it uses functions whose residue classes form a basis of the residue field $k(x)$ , which are simpler to construct.
Normalization: By multiplying basis functions by a carefully chosen function $g_x$ , the algorithm avoids computing large powers of the uniformizer, further reducing computational overhead.

2.3. Application to Gonalities (Section 4)

The gonality algorithm (Algorithm 4.3) iterates through effective divisors $D$ of a target degree $d$ .

It restricts the search to divisors supported on a specific number of rational points (based on Lemma 4.1).
It utilizes the Riemann-Roch theorem to check if $\ell(D) \ge 2$ by computing the rank of the matrix $A$ derived from the precomputed series expansions of a basis of the canonical divisor space $L(K_X)$ .
This replaces the expensive computation of $\ell(D)$ for each divisor with a fast linear algebra operation.

2.4. Application to Class Groups (Section 5)

The class group algorithm (Algorithm 5.3) follows an index calculus approach (Hess's method) but optimizes the relation collection phase.

Factor Basis: A set of closed points $S$ is chosen to generate the class group.
Relation Collection: Instead of generating random small effective divisors, the algorithm fixes a large divisor $D_0$ (with support in $S$ ) and computes spaces $L(D_0 - D)$ for random $S$ -smooth divisors $D$ .
Smoothness Check: A new algorithm (Algorithm 5.2) checks if the divisor of a function is $S$ -smooth by analyzing the zero divisors of the numerator and denominator of the function, avoiding full ideal factorization.
The relations form a lattice, and the class group structure is derived from the Smith normal form of the relation matrix.

3. Key Contributions

Algorithmic Framework: The introduction of a precomputation-based framework that reduces the problem of computing many Riemann-Roch spaces to linear algebra (nullspace/rank computations).
Implementation: Practical implementations of these algorithms in Magma (package CurveArith), which are up to several orders of magnitude faster than existing methods for sufficiently large genus or residue fields.
Optimized Uniformizers: A new procedure (Algorithm 3.2) for computing uniformizing parameters that yields simpler expressions than standard library functions, significantly speeding up series expansion.
Efficient Smoothness Checking: An optimized method for checking the smoothness of function divisors that avoids costly ideal factorization.

4. Results

The authors benchmarked their algorithms against existing methods (Algorithm 4.2 for gonalities and Magma's ClassNumber intrinsic for class groups) on three sets of curves: random plane curves, random space curves, and modular curves $X_0(N)$ .

Gonalities:
- For modular curves $X_0(N)$ , the new algorithm (4.3) achieved speedups of roughly two orders of magnitude compared to the previous method (4.2). For example, computing the gonality of $X_0(154)$ over $\mathbb{F}_5$ took 10 hours with the new method versus an estimated 860 hours with the old method.
- For random curves, the speedup was most pronounced for large genus ( $g \ge 10$ ) and large fields ( $q \ge 30$ ), where runtimes were reduced by over two orders of magnitude.
- The performance gain is driven by the ratio of precomputation cost to the number of divisors tested; when the number of divisors is large, the linear algebra approach dominates.
Class Groups:
- The new algorithm (5.3) generally outperformed Magma's ClassNumber intrinsic, with improvements approaching two orders of magnitude for large genus curves over large fields.
- The improvement is less dramatic than for gonalities because the class group algorithm has a secondary bottleneck: the smoothness check (Algorithm 5.2), which still relies on polynomial and ideal arithmetic. The authors note that the speedup is limited by this step in many cases.

5. Significance and Claims

The paper claims that the primary significance of this work is the provision of explicit, practical implementations that are fast not just in theory but in practice. The authors highlight that previous class group computations often took several hours or even weeks, forcing researchers to abandon certain proof strategies.

The new algorithms enable computations that were previously impractical, such as:

Computing lower bounds on the $\mathbb{Q}$ -gonality for millions of modular curves for the LMFDB.
Extending results on torsion subgroups and rational points to higher degrees and larger fields.

The authors remain modest regarding the limitations, acknowledging that:

The class group algorithm is still bottlenecked by the smoothness check, which they plan to address in future work with a linear algebra-only version.
The performance of the uniformizer computation can still be suboptimal in specific edge cases (e.g., a specific point on $X_0(198)$ ), suggesting that further representation improvements could yield additional gains.
The speedup is most effective when the number of Riemann-Roch spaces to compute is large relative to the precomputation cost; for small genus and small fields, the improvement is negligible.

In summary, the paper presents a shift from direct arithmetic computation to amortized linear algebra, successfully overcoming the scalability barriers that previously hindered the explicit computation of class groups and gonalities for complex curves over finite fields.