# Khuri-Makdisi algorithms for arithmetic in Jacobians#

This module implements Khuri-Makdisi’s algorithms of [Khu2004].

In the implementation, we use notations close to the ones used by Khuri-Makdisi. We describe them below for readers of the code.

Let $$D_0$$ be the base divisor of the Jacobian in Khuri-Makdisi model. So $$D_0$$ is an effective divisor of appropriate degree $$d_0$$ depending on the model. Let $$g$$ be the genus of the underlying function field. For large and medium models, $$d_0\ge 2g+1$$. For small model $$d_0\ge g+1$$. A point of the Jacobian is a divisor class containing a divisor $$D - D_0$$ of degree $$0$$ with an effective divisor $$D$$ of degree $$d_0$$.

Let $$V_n$$ denote the vector space $$H^0(O(nD_0))$$ with a chosen basis, and let $$\mu_{n,m}$$ is a bilinear map from $$V_n\times V_m\to V_{n+m}$$ defined by $$(f,g)\mapsto fg$$. The map $$\mu_{n,m}$$ can be represented by a 3-dimensional array as depicted below:

     f
*------*
d /|e    /|
*-|----* |
| *----|-*
|/     |/
*------*


where $$d=\dim V_n$$, $$e=\dim V_m$$, $$f=\dim V_{n+m}$$. In the implementation, we instead use a matrix of size $$d\times ef$$. Each row of the matrix denotes a matrix of size $$e\times f$$.

A point of the Jacobian is represented by an effective divisor $$D$$. In Khuri-Makdisi algorithms, the divisor $$D$$ is represented by a subspace $$W_D = H^0(O(n_0D_0 - D))$$ of $$V_{n_0}$$ with fixed $$n_0$$ depending on the model. For large and small models, $$n_0=3$$ and $$L = O(3D_0)$$, and for medium model, $$n_0=2$$ and $$L = O(2D_0)$$.

The subspace $$W_D$$ is the row space of a matrix $$w_D$$. Thus in the implementation, the matrix $$w_D$$ represents a point of the Jacobian. The row space of the matrix $$w_L$$ is $$V_{n_0}=H^0(O(n_0D_0))$$.

The function mu_image(w_D, w_E, mu_mat_n_m, expected_dim) computes the image $$\mu_{n,m}(W_D,W_E)$$ of the expected dimension.

The function mu_preimage(w_E, w_F, mu_mat_n_m, expected_codim) computes the preimage $$W_D$$ such that $$\mu_{n,m}(W_D,W_E)=W_F$$ of the expected codimension $$\dim V_n - \dim W_D$$, which is a multiple of $$d_0$$.

AUTHORS:

• Kwankyu Lee (2022-01): initial version

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_base#

Bases: object

multiple(wd, n)[source]#

Compute multiple by additive square-and-multiply method.

negate(wd)[source]#

Theorem 4.4 (negation), first method.

subtract(wd1, wd2)[source]#

Theorem 4.6 (subtraction), first method.

zero_divisor()[source]#

Return the matrix $$w_L$$ representing zero divisor.

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_large[source]#

Khuri-Makdisi’s large model.

Theorem 3.6 (addition of divisors, first method).

We assume that $$w_{D_1}$$, $$w_{D_2}$$ represent divisors of degree at most $$3d_0 - 2g - 1$$.

equal(wd, we)[source]#

Theorem 4.1, second method.

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_medium[source]#

Khuri-Makdisi’s medium model

Theorem 3.6 (addition of divisors, first method).

We assume that $$w_{D_1}$$, $$w_{D_2}$$ represent divisors of degree at most $$4d_0 - 2g - 1$$.

Theorem 5.1 (addflip in medium model).

equal(wd, we)[source]#

Theorem 4.1, second method.

class sage.rings.function_field.khuri_makdisi.KhuriMakdisi_small[source]#

Khuri-Makdisi’s small model

Theorem 3.6 (addition of divisors, first method).

We assume that $$w_{D_1}$$, $$w_{D_2}$$ represent divisors of degree at most $$6d_0 - 2g - 1$$.