# Fast pairings via biextensions and cubical arithmetic

Damien Robert

► To cite this version:

Damien Robert. Fast pairings via biextensions and cubical arithmetic. 2024. hal-04848028

HAL Id: hal-04848028

https://hal.science/hal-04848028v1

Preprint submitted on 19 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fast pairings via biextensions and cubical arithmetic

## Preliminary version for April 1st

DAMIEN ROBERT

**ABSTRACT.** Biextensions associated to line bundles on abelian varieties allows to reinterpret the usual Weil, Tate, Ate, optimal Ate, ..., pairings as monodromy pairings. We introduce a cubical arithmetic, derived from the canonical cubical torsor structure of these line bundles, to obtain an efficient arithmetic of these biextensions.

This unifies and extends Miller's standard algorithm to compute pairings along with other algorithms like elliptic nets and theta functions, and allows to adapt these algorithms to pairings on any model of abelian varieties with a polarisation $\Phi_D$, as long as we have an explicit theorem of the square for $D$.

In particular, we give explicit formulas for the arithmetic of the biextension (and cubical torsor structure) associated to the divisor $D = 2(0_E)$ on an elliptic curve. We derive very efficient pairing formulas on certain models of elliptic curves and Kummer lines. Notably for generic pairings on Montgomery curves, our cubical biextension ladder algorithm to compute pairings costs only $15M$ by bits, which as far as I know is faster than any pairing doubling formula in the literature.

## 1. INTRODUCTION

Pairing based cryptography has been thoroughly optimised over the years, and the pairings are set up via parameters and subgroups tailored for speed. For instance the Tate pairing is restricted to $G_1 \times G_2$ and the embedding degree $d$ is often chosen even to benefit from denominator elimination, we have tools for Miller loop reduction like the Ate and optimal Ate pairing on $G_2 \times G_1$, and so on.

Nevertheless, pairings are important in other aspects than pairing based cryptography, in which case we need to compute “generic pairings”. In particular, for “generic pairings”, we cannot assume that denominator elimination is available, nor that our points $P, Q \in E[\ell]$ are in specific eigenspaces of the Frobenius.

This is notably the case in isogeny based cryptography, where pairings are an important tool. They are used to speed up smooth order DLPs on elliptic curves, generate canonical basis, test the degree of an isogeny, compress messages and signatures, and so on. In these examples the points $P, Q$ are arbitrary points of $\ell$-torsion. We refer to [Rei23] for other examples.

By contrast to pairing based cryptography, pairings are quite slow in the generic case, usually much slower than a curve scalar multiplication. The best formulas I have been able to find in the literature, in [BELL10], uses $10M + 9S$ for doubling, and $11.5M + 3S$ by addition.

### 1.1. Efficient generic pairings on Kummer lines.

In this paper, we introduce a novel algorithm, that is much faster for generic pairings, and is potentially interesting even in the context of pairing based cryptography. We first give a general framework for any elliptic curves and even abelian varieties (not necessarily principally polarised).

Date: July 3, 2024.
Then we focus on the particular case of the Montgomery model. Montgomery elliptic curves $E$, or more precisely their associated Kummer lines $E/\pm 1$, have a very efficient scalar multiplication in the form of the Montgomery ladder, which costs $5M + 4S + 1m_0$ by bits. Here we denote by $M$ a multiplication on the base field, $S$ a square, and $m_0$ a multiplication by a curve constant (which in the case of a Montgomery curve $E: By^2 = x^3+Ax^2+1$ will be the multiplication by $(A+2)/4$. We recall that if $P = (x(P), y(P)) = (X(P) : Y(P) : Z(P))$ in affine (resp. projective) Weierstrass coordinates, its representation on the Kummer line is $x(P)$ (resp. $(X(P) : Z(P))$).

Due to their fast arithmetic (Montgomery curves are also birationally equivalent to twisted Edwards curves, and Curve25519 is also a Montgomery curve), the Montgomery model is usually used in isogeny based cryptography, which makes it a natural target for generic pairing formulas.

For the Montgomery model, our pairing framework gives:

**Theorem 1.1.** Let $E: By^2 = x^3 + Ax^2 + 1$ be an elliptic curve in Montgomery form over a finite field $\mathbb{F}_q$. Let $\ell$ be an integer such that $\mu_\ell \subset \mathbb{F}_q$, $P \in E[\ell](\mathbb{F}_q)$, $Q \in E(\mathbb{F}_q)$. Let $\kappa = 2$ if $\ell$ is odd, and $\kappa = 1$ if $\ell$ is even.

Assume that we are given $\frac{\Lambda+2}{4}$, and the coordinates $x(P), x(Q), x(P+Q)$ and their inverses. Then one can compute a projective representation of the non reduced Tate pairing (i.e., its numerator and denominator) to the power $\kappa$, $e_{T,\ell}(P,Q)^\kappa$, via a cubical biextension ladder which costs $8M + 6S + 1m_0$ by bits.

A similar algorithm holds for the Weil pairing $e_{W,\ell}(P,Q)^\kappa$ when $P,Q \in E[\ell]$, using two cubical biextension ladders rather than one; and also for the Ate and optimal Ate pairings (to the power $\kappa$).

Special cases include:

* When $\ell = 2^m$, or for self pairings when $P = Q$, the cubical biextension ladder costs $5M + 4S + 1m_0$ by bits.

* For batch pairing computations $e_{T,\ell}(P, Q_i)$, with the same base point $P$, after the first pairing the following ones cost $3M + 2S$ by bits for the ladder.

We remark that our cubical biextension ladder cost is much more in line with the cost of the Montgomery Kummer line ladder for scalar multiplication, and that it costs less than the doubling formulas of [BELL10] (which needs to compute additions too!).

An implementation in Sage of Theorem 1.1 (along with many other algorithms) is available at [Rob23b].

**Remark 1.2.**

* Theorem 1.1 is proven in Section 5.2. We also have a variant which uses a more standard double and add algorithm to compute a biextension exponentiation, where each doubling costs $5M + 4S + 1m_0$, but with much more expensive additions of $32M + 4S + 2m_0$ (there is probably still some room for optimisation for the addition, as evidenced by the fact that I also have a DoubleAndAdd formula which costs only $17M + 8S + 3m_0$...). This only makes the double and add approach worthwhile compared to a ladder when using a large enough window (or for $\ell$ of low Hamming weight).

* If $P, Q, P+Q$ are given by their projective $(X(P) : Z(P))$ coordinates on the Kummer line, computing $x(P) = X(P)/Z(P)$, $x(Q) = X(Q)/Z(Q)$, $x(P+Q) = X(P+Q)/Z(P+Q)$ and their inverses only requires one inversion and several multiplications using Montgomery's batch inversion algorithm.
* From $x(P), x(Q), x(P+Q)$, one may only recover $P, Q$ up to a common sign. This involves a square root computation to compute $(P, Q)$ and $(-P, -Q)$. By bilinearity, $e(P, Q) = e(-P, -Q)$, which explains why Theorem 1.1 only needs to know $P, Q, P+Q$ on the Kummer line.

* If we are only given $x(P), x(Q)$ but not $x(P+Q)$, we can only recover the symmetrised pairings $e(P, Q) + e(P, Q)^{-1}$. This involves doing a cubical biextension ladder over the degree two algebra $\mathbb{F}_q[X]/((X-x(P+Q))(X-x(P-Q)))$. This is standard, see [GL08] for elliptic curves, [LR16] for abelian varieties, and also Section 4.7.

* If $E$ is given by a twisted Edwards model, there is a birational map to a Montgomery curve (which by [CGF08] is particularly simple at the level of the Kummer lines: $(Y:Z) \mapsto (Y+Z:Z-Y)$), so we can apply Theorem 1.1.

* During the execution of the standard Miller algorithm for pairings, intermediate zeroes and poles are introduced, which can result in undefined values. Standard solutions are to switch the evaluation point (this does not pose a problem in pairing based cryptography where we have a lot of points, but can be a problem in number theoretic applications when me might have none), or to use Taylor series expansion along a uniformiser (see for instance [Rob21a, Lemma 3.5.3]). By contrast, our cubical biextension ladder is complete, i.e., is always defined, as long as $P, Q, P+Q \neq (0:1)$ (see Remark 5.3).

* We have variants of Theorem 1.1 for different models of Kummer lines. For a level 2 theta model, the complexity of the cubical biextension ladder is $7M + 7S + 2m_0$ by bits (there is a variant with a tradeoff of $1S + 2m_0 - 1M$), see Section 5.3. For a short Weierstrass model, however, the complexity is much worse, at $15M + 8S + 6m_0$ by bits, see Section 5.4.

1.2. **Overview of the algorithm: the practical point of view.** The algorithm proceeds as follows: given the $x$-only coordinates $x(P), x(Q), x(P+Q)$, we can use an extended Montgomery ladder to compute $x(mP), x(mP+Q)$ for any $m > 0$; this costs one doubling and two differential additions by bits.

In practice, to prevent a division at each step, we want to work with projective coordinates $(X(mP) : Z(mP))$ rather than $x(mP)$. Now in the computer, these projective coordinates are represented by affine coordinates, $X(mP), Z(mP)$, and so define a “affine point” $\overline{mP} = (X(mP), Z(mP))$ lying “above” $P$. We will see in Section 4.5 that $\overline{mP}$ is what we call a cubical point, and the coordinates $(X(mP), Z(mP))$ is the affine lift representation of cubical points. And the interesting thing is that there is a well defined cubical arithmetic, which lift the projective arithmetic coming from the addition law on $E$.

So in our pairing algorithm, we compute cubical points $\overline{mP}, m\overline{P}+Q$, using variants of the standard doubling and differential additions which are carefully tailored to give the cubical arithmetic. We will call these variants the cubical or affine doubling and differential additions, and the resulting ladder the cubical ladder or affine ladder.

Now we start with $\overline{P} = (x(P), 1)$, $\overline{Q} = (x(Q), 1)$, $\overline{P}+Q = (x(P+Q), 1)$, and we can use our cubical ladder to compute $\ell\overline{P}+Q$, $\ell\overline{P}$. Since the cubical arithmetic lift the elliptic curve arithmetic, and $\ell P = 0_E$, the point $\ell\overline{P}+Q$ differs from $\overline{Q}$ by some projective factor $\lambda_{P,1}: \ell\overline{P}+Q = \lambda_{1,P}\overline{Q}$, and since $\overline{Q}$ is normalised we have $\lambda_{1,P} = Z(\ell\overline{P}+Q)$. Likewise, $\ell\overline{P}$ lies above the neutral point $0_E = (1:0)$ so is of the form $\ell\overline{P} = (X(\ell\overline{P}), 0) = \lambda_{0,P}(1,0)$.

An important result on cubical arithmetic is that the (square of) the non reduced Tate pairing is precisely given by the monodromy: $e_{T,\ell}(P, Q)^2 = \lambda_{1,P}/\lambda_{0,P} = Z(\ell\overline{P}+Q)/X(\ell\overline{P})$.
The fact that we compute the square of the usual Tate or Weil pairing is not really a problem in practice when $\ell$ is odd (after all for the reduced Tate pairing it suffices to adjust the final exponentiation). But it loses one bit of information when $\ell$ is even. Luckily in this case we can use the action of the theta group $G(2(0_E))$ on cubical points to recover the usual Tate and Weil pairing rather than their squares.

Now when we say that we need to carefully adjust the standard doubling and differential additions formulas on the Montgomery Kummer line to get meaningful cubical arithmetic, as Algorithms 5.4 and 5.5 shows the usual Montgomery ladder is actually already almost the correct cubical ladder! The doubling Algorithm 5.4 is exactly the same. And a minor difference in Algorithm 5.5 is an extra factor of 4, which does not matter for pairings (it does matter for other applications of the cubical arithmetic, like the DLP monodromy leak). The major difference is as follows: both algorithms compute $X(R+S)X(R-S)$, $Z(R+S)Z(R-S)$ from $X(R)$, $Z(R)$, $X(S)$, $Z(S)$, $X(R-S)$, $Z(R-S)$ using exactly the same formulas (up to this factor 4). Now, the usual algorithm, which only cares about projective coordinates, compute $(X(R+S) : Z(R+S)) = (X(R+S)X(R-S)Z(R-S), Z(R+S)Z(R-S)X(R-S))$. For the cubical arithmetic, we really want to use $(X(R+S)X(R-S)/X(R-S), Z(R+S)Z(R-S)/Z(R-S))$, i.e. use two divisions rather than two multiplications. Luckily, during the cubical ladder to compute $\tilde{\mathcal{P}}, \ell \tilde{\mathcal{P}} + \tilde{\mathcal{Q}}$, the base points $R-S$ will be $P, Q$, or $P+Q$. That's why we need the inverses of $x(P), x(Q), x(P+Q)$ in Theorem 1.1, which the usual projective Montgomery ladder does not need; once these have been precomputed, the two divisions by $X(R-S)$ and $Z(R-S)$ only become one multiplication by $1/x(R-S)$ (since our cubical points $\tilde{P}, \tilde{Q}, \tilde{P} + \tilde{Q}$ have been normalised to have $Z=1$).

### 1.3. Overview of the algorithm: the conceptual point of view.
Now we need to explain where this cubical arithmetic which gives pairings come from. We have seen above that our pairings were given by some kind of monodromy information. The correct framework for these monodromy considerations is the concept of biextension.

Biextensions were introduced by Mumford in [Mum69], and their theory thoroughly developed in [Gro72, Exposés VII et VIII]. As mentioned above, biextensions provide the correct theoretical framework to study pairings on abelian varieties and even abelian schemes, and as explained by Grothendieck in [Gro72] allows to keep track of pairing informations on a Néron model even when the special fiber degenerates to a non semi-abelian variety. Notably, he uses biextensions to constructs a pairing between the connected components of the special fiber of the Néron model of an abelian variety $A$ and the one of its dual $\hat{A}$. This pairing is the key in his proof of the semi-stability theorem that an abelian variety always admits a semi-abelian Néron model over a finite field extension.

Now, reading through the 179 pages of abstract cohomological diagram chasing arguments of [Gro72, Exposés VII et VIII] might make biextensions seem like a very abstract theoretical concept, suitable to prove theorems but with no algorithmic applications. This was the impression of the author until recently. Luckily, Stange in [Stao8; Sta11] showed the algorithmic applications of biextensions (in the guise of elliptic nets), and in [Stao8, Theorem 17.1.1] she extends Grothendieck's monodromy interpretation of the Weil-Cartier pairing to the case of the Tate pairing.

And in fact, a biextension is something very concrete. Let us detail the case of the biextension $X_{(0_E)}$ associated to the canonical polarisation $(0_E)$ on an elliptic curve $E$. Let $D = (0_E)$, a biextension element is a tuple $(P, Q, g_{P,Q}) \in X_{(0_E)}$ where $P, Q \in E$ and $g_{P,Q}$ is a function with divisor $D_{P+Q} + D_0 - D_P - D_Q$. Here $D_P$ denotes the divisor $(-P) - (0_E)$ (so $D_0 = 0$ and we will often drop it in the notations). The unusual convention on the signs will be explained in Section 1.6. Modulo our non standard sign convention, the functions $g_{P,Q}$ are
exactly like the functions $\mu_{P,Q}$ we use in pairing based cryptography (which are usually normalised at infinity).

There are two partial group laws $\star_1, \star_2$ on the biextension, which can be used to compute a product $(P_1, Q_1, g_{P_1, Q_1}) \star (P_2, Q_2, g_{P_2, Q_2})$ whenever $Q_1 = Q_2$ for $\star_1$ and whenever $P_1 = P_2$ for $\star_2$. We refer to Equations (9) and (10) for the definitions. A surprising, but very useful fact, is that the biextension $X_{(0_E)}$ is symmetric, which means that $\star_2 = \iota^*\star_1$ where $\iota$ is the swapping of arguments.

Now in the context of the non reduced Tate pairing $e_{T,\ell}(P, Q)$, by [Stao8] its monodromy interpretation via biextensions is as follows: take any rational biextension element $(P, Q, g_{P,Q})$ above $(P, Q)$ and compute the biextension exponentiation $(P, Q, g_{P,Q})^{\star_1, \ell} = (\ell P, Q, g_{\ell P, Q})$. Since $\ell P = 0$, $g_{\ell P, Q}$ has for divisor $D_{\ell P+Q} + D_0 - D_{\ell P} - D_Q = 0$ so is a constant. This constant is precisely $e_{T,\ell}(P, Q)$, or more precisely its class in $\mathbb{F}_q^{\star, \ell}/\mathbb{F}_q^{\star, \ell}$. In Section 3.4 we give a monodromy interpretation of the Ate and optimal Ate pairings; this seems to be new.

To get efficient pairing formulas, we need an efficient representation of biextension elements. The function $g_{P,Q}$ is completely determined, via its divisor, from $P$ and $Q$, up to a constant; so is completely determined by its value at any base point $R_0$. We call this the evaluation representation, and we will see that in Section 3.3 that the biextension exponentiation in the evaluation representation is precisely Miller's algorithm. This subsumes Miller's algorithm in terms of biextension arithmetic.

To go further, we introduce cubical points and the cubical representation of biextension elements. A very informal way of describing the cubical representation, which will be made more rigorous in Section 4.5 is as follows: let $(mP, Q, g_{mP,Q}) = (P, Q, g_{P,Q})^{\star_1, m}$. The function $R \mapsto g_{mP,Q}(R)$ has for divisor $D_{mP+Q} + D_0 - D_{mP} - D_Q$. We can decompose it as a product of “cubical functions”:

$$g_{mP,Q}(R) = \frac{Z(mP + \widetilde{Q} + R)Z(\widetilde{R})}{Z(m\widetilde{P} + R)Z(\widetilde{Q} + R)}$$

where the cubical functions $\widetilde{R} \mapsto Z(mP + \widetilde{Q} + R)$, $\widetilde{R} \mapsto Z(\widetilde{R})$, $\widetilde{R} \mapsto Z(m\widetilde{P} + R)$, $\widetilde{R} \mapsto Z(\widetilde{Q} + R)$, are completely determined from choices of $\widetilde{R}, P+R, \widetilde{Q}+R, \widetilde{P}, \widetilde{Q}, P+Q$ and are “functions” with divisors $D_{mP+Q}, D_0, D_{mP}$, and $D_Q$ respectively. These divisors are not principal, so these “functions” do not make sense on $E$, but they do make sense as cubical functions.

And a way to represent these cubical functions is via their “evaluation” at a base point $\widetilde{R}_0$. So we represent the biextension elements $(P, Q, g_{P,Q})^{\star_1, m}$ by the cubical points

$$[m\widetilde{P} + \widetilde{R}_0, Q + \widetilde{R}_0; \widetilde{R}_0, mP + \widetilde{Q} + R_0].$$

In practice, we will use $R_0 = 0_E$ as our base point since it is the most convenient, and our representation will be given by $[m\widetilde{P}, \widetilde{Q}; \widetilde{0}, m\widetilde{P} + \widetilde{Q}]$.

The link with the previous evaluation representation is: $g_{mP,Q}(0_E) = \frac{Z(m\widetilde{P}+Q)Z(\widetilde{0})}{Z(m\widetilde{P})Z(\widetilde{Q})}$. (Or more rigorously, since $0_E$ is a zero of order 1 of both sides, this becomes an equality after dividing both sides by the same uniformiser).

So using cubical points, we have a way to split the functions $g_{mP,Q}$ as quotients of cubical functions, and a way to split the evaluation representation $g_{mP,Q}(\widetilde{R}_0)$ as a quotient of the evaluation of these cubical functions at $R_0$ (given in practice by the value of $Z$ on suitable cubical points). We formalize this concept of “cubical points” in Section 4; the interesting
things as already mentioned is that cubical points admits a cubical arithmetic (which is not
defined everywhere, nor is given by partial group laws).

This cubical arithmetic arises from the notion of cubical torsor structure, which is de-
veloped in [Bre83] and [Mor85, Chapitre 1]. In particular, Breen introduces in [Bre83] the
concept of symmetric biextension, and explains how a cubical torsor structure give sym-
metric biextensions and conversely. For a biextension $X_D$ associated to a divisor $D$ on an
abelian variety $A$ with structure sheaf $O_A$, and interpreting $D$ as a line bundle $\mathcal{L} = O_A(D)$,
i.e. as a $\mathbb{G}_m$ torsor for the Zariski (or étale or fppf) topology; the theorem of the square
$\mathcal{L}_{a+b} \otimes \mathcal{L} \simeq \mathcal{L}_a \otimes \mathcal{L}_b$ (where $\mathcal{L}_a := t_a^*\mathcal{L}$ and $t_a : A \to A, P \mapsto a+P$ is the translation by $a$)
already gives a squared structure. This squared structure induces a canonical cubical torsor
structure, i.e. isomorphisms $\mathcal{L}_{a+b+c} \otimes \mathcal{L}_{a+b}^{-1} \otimes \mathcal{L}_{b+c}^{-1} \otimes \mathcal{L}_{a+c}^{-1} \otimes \mathcal{L}_a \otimes \mathcal{L}_b \otimes \mathcal{L}_c \otimes \mathcal{L}^{-1} \simeq O_A$
satisfying various natural compatibility conditions; along with higher dimensional structures
(which we won't need). This cubical torsor structure will be used for our cubical arithmetic,
for which we give explicit formulas, and we use these explicit formulas to recover in Theo-
rem 4.16 the fact from [Bre83; Mor85, Chapitre 1] that the cubical torsor structure determines
the symmetric biextension $X_D$.

The story so far is: pairings can be interpreted as monodromy informations on biexten-
sions, this monodromy can be computed via biextension exponentiations, and cubical points
and their arithmetic provide a convenient way to compute the biextension arithmetic. This is
starting to get a bit long winded, and we still need an efficient way to describe our cubical
points and their arithmetic. Thankfully, that's the last step we will need for Theorem 1.1.
We will see in Section 4 that a cubical point $\tilde{P}$ is abstractly a rigidification of our $\mathbb{G}_m$-torsor
(i.e. line bundle) $\mathcal{L}$ at $P$. Going back to the case $\mathcal{L} = O_E(2(0_E))$ of Kummer lines, we have
the two sections $X, Z \in \Gamma(2(0_E))$, which give the projective coordinates $(X(P) : Z(P))$
of a point $P \in E$. We remark that the function $x = X/Z$ is a well defined function on
the elliptic curve. But via our rigidification $\tilde{P} : \mathcal{L}(P) \to O_E(P) = k(P)$ we can interpret
$\tilde{P} \circ X, \tilde{P} \circ Z$ as elements of $k(P)$ and so define their “values” at $P$, which we will denote by
$X(\tilde{P}), Z(\tilde{P})$ (since the values depend on the choice of rigidification $\tilde{P}$ above $P$; changing this
rigidification $\tilde{P}$ to $\lambda \cdot \tilde{P}$ changes the coordinates by a factor $\lambda : X(\lambda \cdot \tilde{P}) = \lambda \cdot X(\tilde{P})$). We call
this the affine lift representation of our cubical point $\tilde{P}$, indeed since $x = X/Z$ is a genuine
function on $E$, we have $X(\tilde{P})/Z(\tilde{P}) = x(P)$, so $(X(\tilde{P}), Z(\tilde{P}))$ is a point in $\mathbb{A}^2$ above the
point $(X(P) : Z(P)) \in \mathbb{P}^1$.

Now as an aside, for our cubical representation, since we use the level 2 coordinates $X, Z \in \Gamma(2(0_E))$, this means that we will be working with the biextension $X_{2(0_E)}$ rather than $X_{(0_E)}$, hence compute the Tate and Weil pairings associated with the divisor $2(0_E)$. This is where the square factor in Theorem 1.1 comes from, compared to the usual Tate and Weil pairings associated to $(0_E)$. We saw in Section 1.2 that we can still compute the standard Tate and Weil pairing when $\ell$ is even while working on $X_{2(0_E)}$, by using the natural action of the theta group $\mathcal{G}(2(0_E))$ on it.

1.4. **Comparison with elliptic nets and the theta coordinates algorithm.** We saw in Section 1.3 that Miller’s algorithm is just a way to compute the arithmetic in biextensions via the evaluation representation.

Elliptic nets [Stao8; Stai1] give an alternative approach to compute pairings, and yet
another approach is given through theta functions [LR10; LR15]. It was already remarked in
[Tra14] that these two approaches are very similar, and how theta functions give “abelian
varieties nets”.
We can go further: both approaches are a way to represent cubical points and their arithmetic. In fact the theta function approach is precisely the affine lift representation of cubical points as defined in Section 1.3, when we use as coordinates a basis $\theta_0, \dots, \theta_m$ of theta functions.

For the elliptic nets approach, the idea is to work with the biextension $X_{(0_E)}$ and so cubical points for $(0_E)$. We only have (up to a scalar) one global section $Z_1 \in \Gamma(0_E)$ (such that in our notations of Section 1.3, $Z = Z_1^2$), but we can still define the value $Z_1(\tilde{P})$ of a cubical point. Given cubical points $\tilde{P}, \tilde{Q}, P+Q$, the cubical arithmetic allows to compute all $mP+nQ$ $m, n \in \mathbb{Z}$, and the associated elliptic net is then $Z_1(mP+nQ)$.

The main drawback of elliptic nets is that $Z_1(\tilde{P})$ is not enough to determine $P$. It is actually quite remarkable though, that thanks to the recurrence relation of elliptic nets, the data of $Z_1(m\tilde{P}+nQ)$ for small values of $m, n$ is enough to recover all of them. In Section 4.9, we introduce another representation of cubical points $\tilde{P}$ for $(0_E)$, which is simply given by $(P, Z_1(\tilde{P}))$. This is enough to completely determine $P$ (obviously), and also $\tilde{P}$ except when $P=0_E$ because in this case $Z_1(0_E) = 0$. We refer to Section 4.9.5 for more details.

In Section 4.9.4, we look at cubical points for $2(0_E)$. We could represent a cubical point $\tilde{P}$ by $(P, X(\tilde{P}), Z(\tilde{P}))$, but since $(X(\tilde{P}), Z(\tilde{P}))$ is already enough to recover $(X(P) : Z(P))$, and since $(X(P) : Z(P))$ completely determines $\pm P$, the values $X(\tilde{P}), Z(\tilde{P})$ are almost enough to determine $\tilde{P}$. Also when $P = 0_E$, $X(\tilde{0}_E) \neq 0$, hence $X, Z$ are enough to determine $\tilde{0}_E$ too. As explained in Section 1.2, this is the representation used for Theorem 1.1.

### 1.5. Applications.
The main goal of the paper is to give efficient generic pairing formulas. But the tools we develop for this, notably the efficient arithmetic of the biextension and cubical points associated to the divisor $2(0_E)$ on an elliptic curve, have applications beyond this goal.

In Section 6 we discuss some of these further applications: pairing based cryptography, radical isogenies, supersingularity testing, and a novel side channel attack which I call the monodromy leak. In particular, while pairings only use the biextension arithmetic, the monodromy leak application of Section 6.4 really needs the full power of the refined cubical arithmetic.

### 1.6. Conventions and notations.
I had two choices when writing this paper. First, develop the general theory of cubical arithmetic for abelian varieties (or even abelian schemes), and then specialize only at the end to elliptic curves. But I feared this would seem too abstract.

The second approach would have been to restrict to elliptic curves only and develop only the biextension and cubical arithmetic associated to the divisors $(0_E)$ and $2(0_E)$. But for the applications mentioned in Section 1.5, I really wanted to develop the general theory of cubical arithmetic over an abelian variety. Besides, isogeny based cryptography uses higher dimensional isogenies more and more, so deriving efficient formulas in any dimension seemed worthwhile.

In the end, I opted for a mix of the two approaches: either first describing the general case and then specializing to elliptic curves, or only detailing the case of elliptic curves and then quickly indicating the generalisation to abelian varieties (or let the reader work them out). This comes at a cost of some redundancy in the exposition, but I hope it will make the exposition more accessible.

I also tried to prove (almost) all statements using the explicit formulas given in this paper, rather than resorting to abstract proofs. Notably, I give explicit formula based proofs that the biextension Weil and Tate pairings are the standard Weil and Tate pairings (up to a sign), and that the cubical arithmetic induces the biextension arithmetic.
One particular conundrum I had in the exposition is the following. On abelian varieties, it is much more convenient to use the language of line bundles $\mathcal{L}$ than the language of divisors $D$. This is because we are almost always only interested in the isomorphism class of $\mathcal{L}$, and it is much easier to work with line bundles up to isomorphisms than to work with divisors up to linear equivalences.

On the other hand, in the case of elliptic curves, divisors have a very convenient representation as a (formal) sum of points (we don't have such convenient representations for abelian varieties). Since pairings on elliptic curves are my main application, I made the choice to work (as much as possible) with divisors.

A side effect is that I need different sign conventions than usual. Indeed, given a line bundle $\mathcal{L}$ on an abelian variety $A$, the polarisation associated to $\mathcal{L}$ is $\Phi_{\mathcal{L}}: A \to \hat{A}, P \mapsto t_P^*\mathcal{L} \otimes \mathcal{L}^{-1}$, where $t_P$ is the translation by $P$. If $\mathcal{L}$ is induced by a divisor $D$, we can rewrite $\Phi_{\mathcal{L}}$ as $\Phi_D: A \to \hat{A}, P \mapsto t_P^*D - D = t_{-P}D - D$ (or rather its linear equivalence class). In particular, the canonical polarisation $\Phi_{(0_E)}$ associated to $E$ on an elliptic curve is $P \mapsto (-P) - (0_E)$. Notice the sign change compared to the usual identification of $E$ and $\hat{E}$! But the one we use in this article is really the correct one according to [Cono4, Example 2.5]. To mitigate this, we introduce the following notation: $D_P := \Phi_D(P) = t_P^*D - D$. This notation has the convenient advantage that a cycle $Z = \sum n_i(P_i)$ on an abelian variety is mapped through $\Phi_D$ to the divisor $\sum n_i D_{P_i}$ (we also have $D_0 = 0$), so we can use a cycle notation for both elliptic curves and abelian varieties.

An apology: I gave up on using the language of divisors in Section 4 to define cubical points. Indeed a cubical point is a rigidification of the line bundle $\mathcal{L}$ at $P$. This can be rephrased in terms of a choice of a non zero local section evaluated at $P$, which can also be described using the language of divisors, but the formalism of rigidifications is much more practical, so I switched languages.

1.7. **Genesis and thanks.** The starting point of this research project was the wonderful paper [CHM+23]. In this paper, the authors use self pairings to find weak instances of class group action isogeny based cryptography.

In a nutshell: assume that $End(E) = \mathbb{Z}[\sqrt{\alpha}]$ is of discriminant $\Delta$ and $\alpha$ is totally imaginary. Then the Weil-Cartier pairing associated to $\alpha$ is a non degenerate pairing $e_\alpha : E[\alpha] \times E[\tilde{\alpha}] \to \mu_\Delta$. Furthermore, $E[\alpha]$ is cyclic (otherwise $\alpha$ would be divisible by an integer), and $\tilde{\alpha} = \overline{\alpha} = -\alpha$, so $E[\alpha] = E[\tilde{\alpha}]$. We obtain a non degenerate self pairing $e_\alpha$ on the cyclic group $E[\alpha]$ which can be used to recover torsion point informations for isogenies arising from the class group action. (In [CHM+23] the authors mainly use the “generalised $\alpha$-Tate pairing” rather than the $\alpha$-Weil-Cartier pairing, but the overall approach is the same.)

An open question in that paper is how to compute this $\alpha$-Weil-Cartier pairing and the generalised $\alpha$-Tate pairing, without going back to the usual Weil and Tate pairings (which can be costly).

At that time, I knew that the arithmetic of theta groups naturally gave rise to the Weil and Tate pairings, so I tried to extend [CHM+23] by looking at theta group informations (not necessarily coming from self pairings) preserved by class group isogenies. This is how I first found the monodromy leak attack of Section 6.4, formulated at the time in term of canonical lift of points of $\ell$-torsion in the theta group rather than in terms of cubical points. I only found out afterwards that Lauter and Stange already had very similar ideas much earlier in [LS08], using the elliptic nets framework.

The key idea to rephrase the theta group approach in terms of biextensions (biextensions are a convenient way to package families of theta groups) is due to Stange, who mentioned
during a discussion last year with the authors of [CHM+23] and myself that elliptic nets were a way to compute the biextension arithmetic, as she had proven in [Sta11, Chapter 15].

Thanks to my work with David Lubicz in [LR10; LR15] on computing pairings via theta functions, I quickly realised that we could define “algebraic Riemann relations” (see Section 4.1) which could also be used to compute the arithmetic of biextensions. Like in our work where we used affine lift of theta points, I could define affine lift of points for any models of abelian varieties, use the algebraic Riemann relations to encode some sort of arithmetic on these affine points, and represent biextension elements via these affine points. Working out the formulas, I found out this generalised not only the theta coordinates approach but also the elliptic nets approach (see Sections 1.4 and 4.9.5), so I knew I was on the right path. I also implemented Theorem 1.1 in Sage in September 2023, and it did indeed compute correctly the pairings (and much faster than Sage’s default implementation)! Trying to make sense of the corresponding arithmetic of these affine lifts of projective points, I found out, thanks to the work of [Bre83] and [Mor85, Chapitre 1], that the correct notion was the cubical torsor structure. Thanks to these firm existing theoretical foundations, extending the work of [Sta11; LR10; LR15] to the general case of cubical points and cubical arithmetic was straightforward.

In summary, this paper owes a lot to Stange and her PhD on elliptic nets, and obviously to Lubicz through our collaboration on [LR10; LR15]. I also benefited from various discussions with Stange and the authors of [CHM+23], notably with Castryck and Vercauteren; and also with Reijnders about [Rei23] and with Guillevic on the current state of the art on pairing based cryptography. Notably, I had not realised before [Rei23] that generic pairings in isogeny based cryptography were so slow; this motivated me to write Theorem 1.1 in the Montgomery model.

I also thank the authors of [CLZ24] for sending me a preliminary version of their pairing formulas. Lastly, special thanks are due to Giacomo Pope who converted my toy Sage implementation from [Rob23b] to an efficient Rust implementation.

We thank Jianming Lin for pointing several typos in the formulas.

1.8. **Related work.** As mentioned, the best generic pairings formula I found in the literature are from [BELL10]. The paper [Rei23] by Reijnders focus specifically on pairings for isogeny based cryptography.

There has been relatively recent work in [DZZZ22; DZZ23] to optimize pairing formula for pairing based cryptography in the odd embedding degree case, which is interesting because this case is closer to the generic case than the even embedding degree case with denominator elimination. This work has been applied to pairings for isogeny based cryptography in [LWXZ23] and very recently the paper [CLZ24] gave fast generic pairing formulas for supersingular curves over $\mathbb{F}_{p^2}$ via Miller's algorithm in modified Jacobian coordinates, with $10M + 7S$ for a Miller doubling and $20M + 11S$ for a Miller double and add.

1.9. **Outline.** We first define the arithmetic of theta groups in Section 2, and how to recover pairings from this arithmetic. We then move on to the theory of biextensions in Section 3, which are a convenient way to package families of theta groups, we also reformulate pairings in terms of monodromy on biextensions. We then introduce cubical points and the cubical arithmetic as a refinement of the biextension arithmetic in Section 4, and we reframe yet again pairings using cubical points. In Section 5 we specialize our formulas to the case of pairings on Kummer lines, and prove Theorem 1.1. We briefly mention some applications in Section 6 and give some perspectives in Section 7.

**Warning:** This paper was supposed to be written soon after my talk on this subject at the Leuven Isogeny Days 4 in October 2023. However, this plan was sidetracked by the
discovery of the Clapotis algorithm, and its applications. Meanwhile, several people have already started using the cubical arithmetic formulas for faster pairing computations in isogeny based cryptography. This current version of the article is a preliminary version that I am publishing as a preprint paper because a larger diffusion of the algorithm to the community is probably worth it. Beside I could not resist the idea of publishing a preliminary version on April first. Beware that there are probably many typos (I mean April fool's!) still.

*Update for April 16:* the paper is now complete; apart from the many remaining typos I still need to correct.

## 2. THETA GROUPS ARITHMETIC

We first introduce theta groups of elliptic curves in Section 2.1 and how to use the theta group arithmetic to compute the usual Weil and Tate pairings associated to the divisor $\mathcal{O}_E$ on elliptic curves in Section 2.2. We briefly describe the general case of pairings on an abelian variety with a polarisation $\Phi_D$ in Section 2.3. As mentioned in Section 1, this general case of handling non necessarily principally polarised abelian varieties will be useful even in the context of elliptic curves, because when $\ell$ is even, we can use the theta group action of $G(2(\mathcal{O}_E))$ to compute the standard Weil and Tate pairing rather than their square even while working with the non principal polarisation $2(\mathcal{O}_E)$.

### 2.1. Theta groups on elliptic curves.
Biextensions are families of theta groups. We first define theta groups and explain their link with pairings, before introducing biextensions. For much more details on theta groups we refer to Mumford [Mum70; Mum66].

Let $k$ be a field and $E/k$ be an elliptic curve, and $D$ a divisor of degree $n$. There is an associated polarisation $\Phi_D: E \to \hat{E}, P \mapsto t_P^*D - D = t_{-P}D - D \simeq D - t_P D$, whose kernel is $\text{Ker } \Phi_D = E[n]$. (If $n=0$, we make the convention that $E[0] = E$.) The theta group $G(D)$ is an extension of $E[n]$ by $\mathbb{G}_m$, defined as follows: its elements are given by couples $(P, g_P) \in G(D)$ where $P \in \text{Ker } \Phi_D$ and $g_P$ is any function whose divisor is the principal divisor $t_P^*D - D$.

For simplicity, we will often refer to the element $(P, g_P) \in G(D)$ simply by the function $g_P$. We will also say that $(P, g_P) \in G(D)(k)$ if $P \in E(k)$ and $g_P$ is defined over $k$. In the special case where $P = \mathcal{O}_E$, the divisor $t_{\mathcal{O}_E}^*D - D$ is trivial, so $g_{\mathcal{O}_E}$ is a constant.

The (non commutative) group law is given by

$$ (1) \qquad (P, g_P) \cdot (Q, g_Q) = (P + Q, g_P \cdot g_Q \cdot (\cdot + P)). $$

There is also a canonical action of $G(D)$ on $\Gamma(D)$, given for $s \in \Gamma(D)$ (i.e. a function such that $\text{div } s + D \ge 0$) by

$$ (2) \qquad (P, g_P) \cdot s = g_P(\cdot)s(\cdot + P). $$

Given two divisors $D_1, D_2$, and an element $P \in \pi_1(G(D_1)) \cap \pi_2(G(D_2))$, where $\pi: G(D) \to E[\deg D]$ is the projection map $(P, g_P) \mapsto P$, we have a morphism:

$$ (3) \qquad (P, g_{1,P}) \in \pi_1^{-1}(P), (P, g_{2,P}) \in \pi_2^{-1}(P) \mapsto (P, g_{1,P}g_{2,P}) \in G(D_1 + D_2). $$

Likewise, if $D_1 \sim D_2$, we have an isomorphism $G(D_1) \simeq G(D_2)$. Namely, if $\alpha$ is any function with divisor $D_2 - D_1$, this isomorphism is given by

$$ (4) \qquad (P, g_P) \in G(D_1) \mapsto (P, g_P(\cdot)\alpha(\cdot + P)/\alpha(\cdot)) \in G(D_2). $$

We remark that the isomorphism does not depend on the choice of $\alpha$.

If $c \in E$, we also have an isomorphism:

$$ (5) \qquad (P, g_P) \in G(D) \mapsto (P, t_c^*g_P) \in G(t_c^*D). $$
**Example 2.1.** Let $D_\ell = \ell(0_E)$ for $\ell \in \mathbb{N}^*$, then $\text{Ker } \Phi_D = E[\ell]$. An element $(P, g_P) \in G(D_\ell)$ above $P \in E[\ell]$ is a function $f_{\ell,P}$ (not necessarily normalised) with divisor $\ell(-P) - \ell(0_E)$.

This is (up to a change of sign in $P$) the usual Miller function involved in the Tate and Weil pairing. Let us explain how to recover the Weil pairing in the context of the theta group $G(D_\ell)$.

Given another element $(Q, g_Q) = f_{\ell,Q} \in G(D_\ell)$, the failure of the commutativity of the group law of $G(D_\ell)$ is measured by the commutator $[(P, g_P), (Q, g_Q)] = (P, g_P)(Q, g_Q)(P, g_P)^{-1}(Q, g_Q)^{-1}$. We compute $(g_P \cdot g_Q)(x) = f_{\ell,P}(x)f_{\ell,Q}(x+P)$ while $(g_Q \cdot g_P)(x) = f_{\ell,Q}(x)f_{\ell,P}(x+Q)$. We thus have $g_P \cdot g_Q = \lambda g_Q \cdot g_P$ with $\lambda = \frac{f_{\ell,P}((x)-(x+Q))}{f_{\ell,Q}((x)-(x+P))}$, for any $x$. Here we use the usual convention for a function $f$ evaluated on a divisor $D = \sum n_i(P_i)$ of degree $0$: $f(D) = \prod f(P_i)^{n_i}$. We recover the usual formula for the Weil pairing $e_{W,\ell}$ (up to a sign depending on the sign convention), which is not surprising since Mumford proves in [Mum70, p. 183] that the commutator pairing is the Weil pairing.

**2.2. Theta groups and pairings for elliptic curves.** We will be mainly interested in the case where $D$ is a degree zero divisor. In this case, $\text{Ker } \Phi_D = E$, the commutator pairing is trivial, so $G(D)$ is a commutative extension of $E$ by $\mathbb{G}_m$.

Up to linear equivalence, we can assume that $D$ is of the form $D = D_Q := \Phi_{(0_E)}(Q) = t_Q^*(0_E) - (0_E) = (-Q) - (0_E) \in \hat{E} := \text{Pic}^0(E)$. The theta group $G(D_Q)$ thus gives an element of $\text{Ext}^1(E, \mathbb{G}_m)$, which gives an explicit isomorphism $\hat{E} \simeq \text{Ext}^1(E, \mathbb{G}_m)$, $D_Q \to G(D_Q)$. Using this isomorphism and the long exact sequence of cohomology, we obtain a canonical isomorphism between $\text{Ker } f, f : E_1 \to E_2$ an isogeny, and the Cartier dual of the kernel $\text{Ker } \hat{f}$ of the dual isogeny. This isomorphism induces the usual Weil-Cartier pairing, and the standard Weil pairing is the Weil-Cartier pairing associated with the polarisation $\Phi_{\ell(0_E)} = \ell\Phi_{(0_E)}$, where $\Phi_{(0_E)} : P \mapsto (-P) - (0_E) \sim (0_E) - (P)$ is the canonical principal polarisation.

**Remark 2.2.** The formula for $\Phi_{(0_E)}$ might seem to be the opposite of the usual isomorphism taken for $E \simeq \hat{E}$, but is the correct one such that the pullback of the Poincare bundle gives an ample line bundle (see [Cono4, Example 2.5]). Since we want our arguments to apply “as is” to abelian varieties, we will stick with this choice. Unfortunately, this means that our sign convention on divisors will be the opposite of the usual ones taken in the pairing literature, for instance our function $\mu_{P,Q}$ will be the normalised (at infinity) function with divisor $(-P - Q) + (0_E) - (-P) - (-Q)$. If $\mu_{P,Q}$ is the usual normalised function with divisor $(P) + (Q) - (P + Q) - (0_E)$, we have $\mu_{P,Q}(R) = 1/\mu_{P,Q}(-R)$.

We now explain how to recover the Weil and Tate pairing from our theta groups $G(D_Q)$. If $P \in E$, we will denote by $g_{P,Q} \in G(D_Q)$ an element in the theta group above $P$; its divisor will then be $t_P^*D_Q - D_Q = D_{P+Q} - D_P - D_Q = (-P - Q) + (0_E) - (-P) + (-Q)$. The function $g_{P,Q}$ then also gives an element of $G(D_P)$ above $Q$.

Now, given $P_1, P_2 \in E$ and two functions $g_{P_1,Q}, g_{P_2,Q} \in G(D_Q)$ above $P_1, P_2$ respectively, we have two possible group operations. The first one is given by the multiplication

$$ (6) \qquad (P_1, g_{P_1,Q}) \cdot (P_2, g_{P_2,Q}) = (P_1 + P_2, g_{P_1,Q}(\cdot)g_{P_2,Q}(\cdot + P_1)) $$

in the theta group $G(D_Q)$. The second one is to interpret $(Q, g_{P_1,Q})$ as an element of $G(D_{P_1})$ above $Q$ and use Equation (3) to get an element $(Q, g_{P_1,Q}(\cdot)g_{P_2,Q}(\cdot))$ above $Q$ in the theta group $G(D_{P_1} + D_{P_2})$. Now $D_{P_1} + D_{P_2} \simeq D_{P_1+P_2}$, so if $g_{P_1,P_2}$ is any function with divisor $D_{P_1+P_2} - D_{P_1} - D_{P_2} = (-P_1 - P_2) + (0_E) - (-P_1) - (-P_2)$ then by Equation (4) we have an
isomorphism $G(D_{P_1} + D_{P_2}) \simeq G(D_{P_1+P_2}), (Q, g_Q) \mapsto (Q, g(\cdot)g_{P_1,P_2}(\cdot+Q)/g_{P_1,P_2}(\cdot))$. Composing this isomorphism with the map above, we get an element $(Q, g) \in G(D_{P_1+P_2})$ which induces an element $(P_1 + P_2, g_{P_1+P_2,Q}) \in G(D_Q)$. This gives us the second group operation:

$$ (7) \quad (P_1, g_{P_1,Q})' (P_2, g_{P_2,Q}) = \left( P_1 + P_2, g_{P_1,Q}(\cdot) g_{P_2,Q}(\cdot) \frac{g_{P_1,P_2}(\cdot+Q)}{g_{P_1,P_2}(\cdot)} \right). $$

It is not obvious, but Equations (6) and (7) actually give the same group law:

**Proposition 2.3.** $(P_1, g_{P_1,Q})' (P_2, g_{P_2,Q}) = (P_1, g_{P_1,Q}) (P_2, g_{P_2,Q}) = (P_1 + P_2, g_{P_1+P_2,Q})$.

*Proof.* This follows from the unicity of the biextension associated to the principal polarisation $\Phi_{(0_E)}$, see Proposition 3.4 and Equation (11). $\square$

**Corollary 2.4.** Let $(P, g_{P,Q}) \in G(D_Q)$. Then $(P, g_{P,Q})^\ell = (\ell P, g_{P,Q}(\cdot)^\ell f_{\ell,P}((\cdot+Q)-\cdot))$, where $f_{\ell,P}$ is a function with divisor $D_{\ell P} - \ell D_P = -\ell(-P) + (-\ell P) + (\ell - 1)(0_E)$.

*Proof.* By Proposition 2.3, we can use Equation (7) rather than Equation (6) when computing $(P, g_{P,Q})^\ell$. We obtain $(P, g_{P,Q})^\ell = (\ell P, g_{P,Q}(\cdot)^\ell (g_{P,P}g_{P,2P} \cdots g_{P,(\ell-1)(P)}((\cdot+Q)-\cdot))$ and we observe that $(g_{P,P}g_{P,2P} \cdots g_{P,(\ell-1)(P)})$ has for divisor $D_{\ell P} - \ell D_P$. $\square$

**Corollary 2.5.** If $P, Q \in E[\ell]$, take any $(P, g_{P,Q}) \in G(D_P)$, and let $\lambda_P$ the constant such that $(P, g_{P,Q})^\ell = (0_E, \lambda_P)$ (alternatively, $(P, g_{P,Q})^{\ell+1} = (P, \lambda_P g_{P,Q})$). Likewise, let $\lambda_Q$ be the constant such that $(Q, g_{P,Q})^\ell = (0_E, \lambda_Q)$, where $(Q, g_{P,Q}) \in G(D_Q)$. Then (up to a sign), the Weil pairing $e_{W,\ell}(P, Q) = \lambda_P/\lambda_Q$.

Assume that $k = \mathbb{F}_q$, $\mu_\ell \subset \mathbb{F}_q$, and let $\mathcal{Q} \in E(\mathbb{F}_q)$, $P \in E[\ell](\mathbb{F}_q)$. Take any $(P, g_{P,Q}) \in G(D_Q)(\mathbb{F}_q)$. Then $(P, g_{P,Q})^\ell = (0_E, \lambda_P)$ where $\lambda_P$ is (up to a sign) the non reduced Tate pairing $e_{T,\ell}(P, Q)$. And $(P, g_{P,Q})^{q-1} = (0_E, \lambda'_P)$ (alternatively, $(P, g_{P,Q})^q = (P, \lambda'_P g_{P,Q})$), where $\lambda'_P$ is the reduced Tate pairing.

*Proof.* This follows from Corollary 2.4 and the usual formulas for the Tate and Weil pairing.

Indeed, we have $\lambda_P/\lambda_Q = \frac{g_{P,Q}(\cdot)^\ell f_{\ell,P}((\cdot+Q)-\cdot)}{g_{P,Q}(\cdot)^\ell f_{\ell,Q}((\cdot+P)-\cdot)} = e_{W,\ell}(P, Q)$, and $\lambda_P = g_{P,Q}(\cdot)^\ell f_{\ell,P}((\cdot+Q) - \cdot)$ is equivalent to the non reduced Tate pairing $f_{\ell,P}((\cdot+Q) - \cdot)$ since $g_{P,Q}$ is assumed to be rational.

For the last statement, we remark that $(P, g_{P,Q})^{q-1} = ((P, g_{P,Q})^\ell)^{(q-1)/\ell} = (0_E, \lambda_P)^{(q-1)/\ell} = (0_E, \lambda_P^{(q-1)/\ell})$.

As a corollary, we see that $\lambda_P/\lambda_Q$ does not depend on the choice of $g_{P,Q}$, and likewise for the class of $\lambda_P$ modulo $\mathbb{F}_q^{*,\ell}$. This can be directly seen as follows: changing $g_{P,Q}$ by $\lambda_P g_{P,Q}$ changes $\lambda_P$ to $\lambda^\ell \lambda_P$. $\square$

**Example 2.6 (Radical isogenies).** Let $P \in E[\ell]$ of exact order $\ell$, and consider the isogeny $\phi : E \to E' = E/(\langle P \rangle)$. By descent theory [Mum66, Proposition 1 p. 291], the divisor $D_Q$ descends to $E'$ (i.e., there exists some rational degree 0 divisor $D'$ such that $\phi^*D' = D_Q$) if and only if the kernel $\text{Ker } \phi$ lifts to a rational subgroup in the theta group $G(D_Q)$. Since $\text{Ker } \phi$ is cyclic, this is equivalent to finding a rational element $(P, g_P) \in G(D_Q)$ above $P$ of order $\ell$.

Take $g_P \in G(D_Q)(k)$ an arbitrary rational element. We have $(P, g_P)^\ell = (0_E, \lambda_P)$ where $\lambda_P$ is the non reduced Tate pairing by Corollary 2.5. And $(P, \mu g_P)^\ell = (0_E, \mu^\ell \lambda_P)$. It follows that we can find a rational $g_P$ of order $\ell$ if and only the non reduced Tate pairing $e_{T,\ell}(P, Q)$ is an $\ell$-th power.
Now by definition of the dual isogeny $\hat{\phi}$, we have $\hat{\phi}(D') = \phi^*(D_Q)$. We have proved that $\hat{\phi}^{-1}(D_Q)$ contains a rational point $D'$ if and only if the non reduced Tate pairing is an $\ell$-th power. We recover (a special case of) the geometric interpretation from [Rob23c] of the Tate pairing as an étale torsor.

**Example 2.7** (The Tate pairing as an obstruction to finding rational elements of $\ell$-torsion in the theta group). Let $D = \ell(0_E)$ and $P \in E[\ell]$ a point of $\ell$-torsion. A natural question is whether there is an element $(P, g_P) \in G(D)$ which is both rational and still of $\ell$-torsion. (Equivalently: the group $K = \langle P \rangle$ admits a rational lift to $G(D)$, hence by descent theory $D$ descends to a rational divisor on $E/K$.)

The divisor $D$ is symmetric, so we can even ask for symmetric lifts of order $\ell$. If $\ell$ is odd, there are two symmetric elements above $P$, and a unique one of order $\ell$, which has to be rational by unicity.

If $\ell$ is even, the symmetric elements are of order $\ell$ or $2\ell$; this obstruction is measured by $e_{D,\star}(\ell/2\cdot P) = \pm 1$ in the notation of [Mum66, p.307-309]. For our divisor, $e_{D,\star}(\ell/2\cdot P) = 1$, so the two symmetric elements are of order $\ell$. But they might live in a quadratic extension.

Let $g_P$ be an arbitrary theta group element above $P$. We can compute $(P, g_P)^\ell$, this is a constant $\lambda_P$, equal to $g_P(x)g_P(x+P)g_P(x+2P)\cdots g_P(x+(\ell-1)P)$. We can correct $g_P$ by a rational projective factor $\alpha$ so that $(P, \alpha g_P)$ is of $\ell$-torsion if and only if $\lambda_P \in k^{*,\ell}$. Since $g_P$ has for divisor $D_P = \ell(-P) - \ell(0_E)$, we see that the class of $\lambda_P$ in $k^*/k^{*,\ell}$ is given by (the non reduced Tate pairing): $\prod_{i=1}^{\ell-1} g_P(x+iP)/g_P(x) = \prod_{i=1}^{\ell-1} e_{T,\ell(0_E)}(P, iP) = e_{T,\ell(0_E)}(P, \ell(\ell-1)/2P)$.

In particular, we see that the obstruction vanishes for $\ell$ odd (as we already knew), and that for $\ell$ even, the quadratic obstruction is given by whether the reduced Tate pairing of $P$ and $\ell/2 \cdot P$ is equal to 1 or -1.

We already saw $\lambda_P$ in [RS24, § 3.1] for the case $\ell = 2$, where the same obstruction governed the possible formulas for a 2-isogeny on a Kummer line.

## 2.3. Theta groups and pairings for polarized abelian varieties.
As explained in the introduction, for simplicity we mainly work with elliptic curves, but we carefully state our results such that they are easily adapted for any abelian varieties.

In this section, we briefly explain what happens for a general polarised abelian variety $(A, \Theta_A)$, with $\Theta_A$ an ample divisor. Usually when working with abelian varieties, it is more convenient to work with (isomorphisms classes of) line bundles than (linear equivalence classes of) divisors, because unlike for elliptic curves divisor do not have a convenient description. Here for the sake of uniformity we stick to divisors.

Fix any divisor $D$. There is a morphism associated to $D$, $\Phi_D : A \to \hat{A}, P \mapsto t_P^*D - D$, it only depends on the algebraic equivalence class of $D$. We denote by $A[D]$ its kernel. We remark that $\Phi_D$ is a polarisation when $D = \Theta_A$ is ample. If $D = n\Theta_A$, with $\Theta_A$ ample giving a principal polarisation, then $A[D] = A[n]$.

For simplicity, we will use the same notation to denote $\Phi_D(P)$ as the divisor $D_P := t_P^*D - D$, and as an element of $\hat{A} = \text{Pic}^0(A)$, i.e. as a linear equivalence class.

An element $(P, g_P)$ of the theta group $G(D)$ is given by a point $P \in A[D]$ and a function with divisor $D_P := \Phi_D(P)$, with group law given by Equation (1), and natural action on sections given by Equation (2). Equations (3) and (4) also apply for abelian varieties.

### 2.3.1. Pairings on an abelian variety.
We first introduce the Weil-Cartier pairing for an abelian variety.

The reader can skip without harm the following paragraph, which will only serve as a motivation for the notion of biextension in Section 3.1. Let $A/k$ be an abelian variety, and
$B\mathbb{G}_m = [\text{Spec } k/\mathbb{G}_m]$ be the classifying stack associated to $\mathbb{G}_m$ (say for the fppf topology). Then we define $\hat{A}/k$ to be $\text{Hom}(A, B\mathbb{G}_m)$, where we require the morphisms to be morphisms of Picard stacks. By definition of the classifying stack $B\mathbb{G}_m$, a morphism of stack $A \to B\mathbb{G}_m$ corresponds to a $\mathbb{G}_m$-torsor, i.e. a line bundle $\mathcal{L}$. Requiring the morphism to be a morphism of Picard stack imposes $\mathcal{L}$ to be translation invariant (and rigidifies it). Since translation invariant line bundles are the same as the ones which are algebraically equivalent to 0, this gives an isomorphism $\text{Pic}^0(A) = \hat{A} = \text{Hom}(A, B\mathbb{G}_m)$. Now by general abstract nonsense, we have an isomorphism $\text{Hom}(A, B\mathbb{G}_m) = \text{Ext}^1(A, \mathbb{G}_m)$ as fppf sheafs. If $f: A \to B$ is a morphism of abelian varieties, $K = \text{Ker } f$, applying the derived functor $\mathcal{R}\text{Hom}(\cdot, \mathbb{G}_m)$ to the exact sequence $0 \to K \to A \to B \to 0$ gives a distinguished triangle in the derived category, whose associated long exact sequence is $0 \to \text{Hom}(B, \mathbb{G}_m) \to \text{Hom}(A, \mathbb{G}_m) \to \text{Hom}(K, \mathbb{G}_m) \to \text{Ext}^1(B, \mathbb{G}_m) \to \text{Ext}^1(A, \mathbb{G}_m) \to \dots$. Since $\text{Hom}(A, \mathbb{G}_m) = 0$ because $A$ is proper and $\mathbb{G}_m$ affine, and $\text{Ext}^1(B, \mathbb{G}_m) \to \text{Ext}^1(A, \mathbb{G}_m)$ is the dual isogeny $\hat{f}$ via the identification above, we see that $\text{Ker } \hat{f} \simeq \text{Hom}(K, \mathbb{G}_m)$ is canonically isomorphic to the Cartier dual of $K$. This abstract isomorphism gives the Weil-Cartier pairing $e_f: \text{Ker } f \times \text{Ker } \hat{f} \to \mathbb{G}_m$, via the identification above and the canonical pairing from Cartier duality: $K \times \text{Hom}(K, \mathbb{G}_m) \to \mathbb{G}_m$. The standard Weil pairing is the Weil-Cartier pairing applied to the isogeny $[\ell]$.

We now recall the explicit definition of the Weil and Tate pairing associated to the polarisation $\Phi_\Theta$ associated to an ample divisor $D = \Theta = \Theta_A$. For more details, we refer to [Rob21b, Chapter 4; Rob21a, Chapter 3; Rob23c] and the references there. The Weil pairing $e_{W,\Theta,\ell}: A[\ell\Theta] \times A[\ell\Theta] \to \mathbb{G}_m$ associated to $\Phi_\Theta$ is the Cartier Weil pairing associated to the polarisation $\ell\Phi_\Theta: A \to \hat{A}$, and it is also the commutator pairing on the theta group $G(\ell\Theta)$. If $(P, Q) \in A[\ell]$, and $e_{W,\ell}$ is the usual Weil pairing on $A[\ell] \times \hat{A}[\ell]$, we have $e_{W,\Theta,\ell}(P, Q) = e_\ell(P, \Phi_\Theta(Q))$. Likewise, the Tate pairing $e_{T,\Theta,\ell}: A[\ell\Theta](k) \times \hat{A}(k)/(\ell\Phi_\Theta A(k)) \to H^1(k, \mu_\ell)$ is the Tate-Cartier pairing associated to the polarisation $\ell\Phi_\Theta: A \to \hat{A}$. If $P \in A[\ell](k)$, $e_{T,\Theta,\ell}(P, \Phi_\Theta(Q)) = e_{T,\ell}(\Phi_\Theta(P), Q)$, where $e_{T,\ell}$ is the standard Tate pairing associated to the isogeny $[\ell]: A \to A$. If $\Theta = m\Theta_1$, and $P, Q \in A[\ell]$ (resp. $P \in A[\ell](k)$), we have $e_{W,\Theta,\ell}(P, Q) = e_{W,\Theta_1,\ell}(P, Q)^m$, $e_{T,\Theta,\ell}(P, Q) = e_{T,\Theta_1,\ell}(P, Q)^m$.

Formulas are as follows: let $Z_P, Z_Q$ be any degree 0 0-cycles equivalent to $(P) - (0)$ and $(Q) - (0)$, and $D_{Z_P}, D_{Z_Q} = \Phi_\Theta(Z_P), \Phi_\Theta(Z_Q)$. Here we extend $\Phi_\Theta$ to cycles by additivity; by the theorem of the square their linear equivalence class only depends on $P, Q$.

Explicitly, if $Z = \sum n_i(P_i)$ is of degree 0, $D_Z := \sum n_i(t_p^*D - D) = \sum n_i D_{P_i}$ (and we remark that $D_P = D_{(P)-(0)}$). The divisor $D_Z$ is principal if and only if $s(Z) := \sum n_i P_i \in A[D]$, in which case we will write $f_Z$ or $f_{D_Z}$ a function with divisor $D_Z$. In particular, $D_Z \sim D_{s(Z)}$.

We remark that if $P \in A[\ell\Theta]$, then by definition $\ell D_{Z_P} \sim \ell\Phi_\Theta(P)$ is a principal divisor; and by definition $f_{\ell Z_P}$ is any function with this divisor. We will evaluate it on degree 0 cycles, so the evaluation does not depends on the choice of $f_{\ell Z_P}$. We will also denote by $f_{\ell,P}$ the function associated to the divisor $D_{\ell P} - \ell D_{P}$ associated to the cycle $(\ell P) + (\ell - 1)0 - \ell(P)$.

We have

$$e_{T, \Theta, \ell}(P, Q) = f_{\ell Z_P}(Z_Q) \in k^* / k^{*, \ell}$$

if $Q \in A[\ell\Theta](k)$ and

$$e_{W, \Theta, \ell}(P, Q) = f_{\ell Z_P}(Z_Q) / f_{\ell Z_Q}(Z_P) \in \mathbb{G}_m$$
if $P, Q \in A[\ell\Theta]$. (As the proof of Theorem 2.9 will show, we even have $e_{W,\Theta,\ell}(P, Q) = f_{\ell Z_P}(t_X^* Z_Q)/f_{\ell Z_Q}(t_X^* Z_P)$ as long as we translate by the same point $x \in A$.)

Finally we remark that the formulas also holds for any divisor $D$ instead of an ample divisor $\Theta$, but in this case we won't have non degeneracy.

**Remark 2.8.** When we evaluate a function $f$ at some cycle $Z$, it might happen that some of the points $P$ in the support of $Z$ are zeroes or poles of $f$. One way to still define the evaluation $f(Z)$ is to fix a uniformiser $\pi_P$ at these points $P$, and to define $f(P)$ as the value of $(f/\pi_P^{v_P(f)})(P)$. We sometimes call this the extended value. We will see in the monodromy interpretation of pairings from Section 3 that our pairings will be obtained as a quotient of two functions $f_1, f_2$ which differ by a constant $c$. If we represent $f_1, f_2$ by their extended value at $P$, as long as we pick the same uniformizer $\pi_P$ both for $f_1, f_2$, this constant $c$ will be correctly determined by the extended value $f_1(P)/f_2(P)$ even if $P$ is a pole or zero of the $f_i$.

**2.3.2. Pairings via theta groups.** We have seen in Section 2.2 that the map $D_Q = (-Q) - (0_E) \in \text{Pic}^0(E) \mapsto G(D_Q) \in \text{Ext}^1(E, \mathbb{G}_m)$ gives an *explicit isomorphism* $\hat{E} := \text{Pic}^0(E) \simeq \text{Ext}^1(E, \mathbb{G}_m)$. This extends to abelian varieties: the canonical isomorphism $\hat{A} \simeq \text{Ext}^1(A, \mathbb{G}_m)$ is given by $D \in \text{Pic}^0(A) \mapsto G(D)$. We can thus extend Corollary 2.5 to abelian varieties.

We fix $D$ a divisor, and recall that we denote by $D_Q$ the divisor $\Phi_D(Q) = t_Q^*D - D$. The theta group $G(D_Q)$ is an abelian extension of $A$ by $\mathbb{G}_m$, whose elements are given by $(P, g_{P,Q})$ with $P \in A$ and $g_{P,Q}$ a function with divisor $t_P^*D_Q - D_Q = t_{P+Q}^*(D) + D - t_P^*D - t_Q^*D = D_{P+Q} - D_P - D_Q$. The group laws Equations (6) and (7) still hold for $G(D_Q)$, and they are the same because Proposition 2.3 is also valid.

The only subtlety now is that if $P \in A[\ell\Theta]$ and we take $(P, g_{P,Q}) \in G(D_Q)$, then $(P, g_{P,Q})^\ell = (\ell P, g_{\ell P,Q})$ needs not be given by a constant function $g_{\ell P,Q} = \lambda_P$, because $P$ is not necessarily of $\ell$-torsion. However, $\ell P \in A[D]$, and we are able to use the action of theta groups on sections.

**Theorem 2.9.** Let $D$ be a divisor on an abelian variety $A$, $Q \in A$, and $D_Q = \Phi_D(Q)$. Let $(P, g_{P,Q}) \in G(D_Q)$, with $P \in A[\ell D]$. Let $(\ell P, g_{\ell P}) \in G(D)$ be any element above $\ell P$. Let $g_{\ell P,Q}$ be such that $(P, g_{P,Q})^\ell = (\ell P, g_{\ell P,Q})$. Then $g_{\ell P,Q} g_{\ell P}((\cdot) - (\cdot + Q))$ is a constant $\lambda_P$. If $Q \in A[\ell D]$, the Weil pairing is (up to a sign) $e_{W,D,\ell}(P, Q) = \lambda_P / \lambda_Q$.

If $P \in A[\ell D](k)$ and we take $g_{P,Q}, g_{\ell P}$ rational, then the non reduced Tate pairing is given by (up to a sign) $e_{T,D,\ell}(P, Q) = \lambda_P$.

We remark that $(Q, g_{\ell P, Q}) \in G(D_{\ell P})$ and that $g_{\ell P}^{-1}$ is a section of $D_{\ell P}$. By Equation (2), the constant $g_{\ell P, Q} g_{\ell P}((\cdot) - (\cdot + Q))$ is given by $\frac{(Q, g_{\ell P, Q}) \cdot g_{\ell P}^{-1}}{g_{\ell P}^{-1}}$.

*Proof.* First the function $g_{\ell P, Q}$ has for divisor $D_{\ell P+Q} - D_{\ell P} - D_Q$, while $g_{\ell P}$ has for divisor $D_{\ell P}$, so $g_{\ell P}((\cdot) - (\cdot + Q))$ has for divisor $D_{\ell P} - (\bar{D}_{\ell P+Q} - D_Q)$. Their multiplication has trivial divisor, so is a constant.

Now the same proof as in Corollary 2.4 shows that $g_{\ell P, Q} = g_{P, Q}^{\ell} f_{\ell, P}((\cdot + Q) - (\cdot))$ with $f_{\ell, P}$ a function with divisor $D_{\ell P} - \ell D_P$. The function $f_{\ell, P}/g_{\ell P}$ has for divisor $-\ell D_P$. We now conclude as in Corollary 2.5, using the formulas for the Weil and Tate pairings associated to $D$. $\square$

As a consequence of the definitions and the proof of Theorem 2.9, we have the following result which will be useful to get algorithms to compute the Ate and optimal Ate pairings.
**Porism 2.10.** Let $(P_1, g_{P_1,Q}) \in G(D_Q)$, $(P_2, g_{P_2,Q}) \in G(D_Q)$, and $(P_1+P_2, g_{P_1+P_2,Q} \in G(D_Q)$ be their product. Let $g_{P_1,P_2}$ be a function with divisor $D_{P_1+P_2} - D_{P_1} - D_{P_2}$. Then $g_{P_1,P_2}$ evaluated on the cycle $(R+Q)-(R)$ is given by $\frac{g_{P_1+P_2,Q}}{g_{P_1,Q}g_{P_2,Q}}(R)$.

For any $P, Q$, let $(P, g_{P,Q}) \in G(D_Q)$, $(P, g_P)^\ell = (\ell P, g_{\ell P,Q})$, and let $f_{\ell,P}$ a function with divisor $D_{\ell P} - \ell D_P$. Then the function $f_{\ell,P}$ evaluated on the cycle $(R+Q)-(R)$ is given by $\frac{g_{\ell P,Q}}{g_{P,Q}^\ell}(R)$.

$$ \text{And if } P \in A[\ell D], f_{-\ell D_P}((R+Q)-(R)) = \frac{g_{\ell P,Q}}{g_{P,Q}^\ell}(R)g_{IP}((R)-(R+Q)). $$

**Remark 2.11.** The reason we need to go through the trouble of explaining how to compute the Weil and Tate pairing associated to some divisor $D$ on the full $A[\ell D]$ rather than just $A[\ell]$ is the following.

In Section 5, to compute pairings on Kummer lines, we will use the biextension and cubical arithmetic associated to the divisor $D = 2(0_E)$ to compute $e_{W,2(0_E),\ell}, e_{T,2(0_E),\ell}$. On the $\ell$-torsion, these are the square of the usual Weil and Tate pairings $e_{W,(0_E),\ell}, e_{T,(0_E),\ell}$. This is not a really a problem when $\ell$ is odd, but this lose one bit of information when $\ell$ is even.

Instead, in this case we will write $\ell = 2m$, and use the fact that since $m\Phi_{2(0_E)} = \ell\Phi_{(0_E)}$, then by the standard compatibility between pairings and isogenies, we have $e_{W,2(0_E),m} = e_{W,(0_E),\ell}, e_{T,2(0_E),m} = e_{T,(0_E),\ell}$. But $E[m]$ is a strict subset of $E[\ell] = E[m(2(0_E))]$, so we need the full generality of Theorem 2.9 to handle this case properly.

One needs to be careful with the Tate pairing, because of its arithmetic nature (by contrast of the geometric nature of the Weil pairing). Let us assume that $D = mD_1$, $D_1$ a divisor associated to a principal polarisation. In Theorem 2.9, for the Weil pairing, when $P, Q \in A[\ell D] = A[\ell m]$, we correctly compute $e_{W,\ell D}(P, Q) = e_{W,\ell m D_1}(P, Q) \in \mu_{\ell m}$ via the monodromy.

However, the non reduced Tate pairing $e_{T,\ell m D_1}(P, Q) \in k^*/k^{*,\ell}$ is computed in a smaller group than $e_{T,\ell m D_1}(P, Q) \in k^*/k^{*,\ell m}$.

Looking at the formula from Theorem 2.9 and Porism 2.10, we see that to get a value in $k^*/k^{*,\ell m}$ when using the divisor $D$, we need to also keep track of $g_{P,Q}^\ell$; the monodromy information $\lambda_P$ is not enough (it only gives the information in $k^*/k^{*,\ell}$).

More precisely, we have $e_{T,\ell m D_1}(P, Q) = f_{-\ell D_P}((R+Q)-(R)) = \frac{g_{\ell P,Q}}{g_{P,Q}^\ell}(R)g_{IP}((R)-(R+Q)) \in k^*/k^{*,\ell m}$ (for any $R \in A(k)$), where $g_{\ell P,Q}(R)g_{IP}((R)-(R+Q))$ is the monodromy constant $\lambda_P$, and $\frac{1}{g_{P,Q}^\ell}(R)$ is the correcting factor to have the pairing in $k^*/k^{*,\ell m}$.

There is a special case where we can compute the correct value in $k^*/k^{*,\ell m}$ just from the monodromy information. We have a map $G(D_1,Q) \to G(D_Q)$ given by $g_{P,Q} \mapsto g_{P,Q}^{\otimes m}$, where the tensor product $g_{P,Q}^{\otimes m}$ is simply given by the function product: $g_{P,Q}^{\otimes m}(x) = g_{P,Q}(x)^m$. If, when applying Theorem 2.9, our $g_{P,Q} \in G(D_Q)$ comes from the $m$-th tensor product of a rational theta group element in $G(D_1,Q)$, then the monodromy $\lambda_P$ naturally gives the correct value of the Tate pairing $k^*/k^{*,\ell}$, because $g_{P,Q}^\ell(R)$ is then already in $k^*, \ell m$.

One last subtlety about the Tate pairing. For the Weil pairing $e_{W,\ell D}$, replacing $D$ by an equivalent divisor $D'$ still give the correct value $e_{W,\ell m D_1}$, not only on $A[\ell]$ but even on $A[\ell D]$. However, for the Tate pairing, for this to be the case, we need that $D' = mD'_1$, with $D'_1$ a rational divisor. (In particular, the class of $D'_1 - D_1 \in \text{Pic}^0(A)$ is a point of $m$-torsion.) Indeed, when this is the case, we have $f_{\ell D_P}((Q) - (0))/f_{\ell D'_P}((Q) - (0)) = f_{\ell m(D_1-D'_1)_P}((Q) - (0))$, and since $D_1$ is algebraically equivalent to $D'_1$, $D_1, P$ is linearly
equivalent to $D'_{1,p}$, so $f_{lm(D_1-D'_1)_p}$ is a $ml$-th power. So we get the same value for the non-reduced Tate pairing by using $D$ or $D'$. $k(A)$).

### 3. BIEXTENSIONS ARITHMETIC

We define biextensions in Section 3.1, and interpret the Weil and Tate pairing as monodromy pairings in Section 3.2 (as already shown by Grothendieck and Stange respectively). We explain how to recover Miller's standard algorithm in terms of biextensions in Section 3.3, and we give a monodromy interpretation of the Ate and optimal Ate pairings in Section 3.4.

#### 3.1. Biextensions.
Biextensions were introduced by Mumford in [Mum69]. For a complete (but quite dry) reference, we refer to [Gro72, Exposés VII et VIII]. Beware of some sign errors in [Gro72, pp. VIII 2.3.10], corrected in [BBM79, § 5.1].

Let us first give an informal motivation for the notion of biextension. Pairings are bilinear maps. When working with modules, it is much more convenient to interpret a bilinear map $B: G_1 \times G_2 \to G_3$ as an element of $\operatorname{Hom}(G_1 \otimes G_2, G_3)$ than as an element of $\operatorname{Hom}(G_1, \operatorname{Hom}(G_2, G_3))$. In other words: we want the decurryfication of the map $G_1 \to G_2 \to G_3$, $g_1 \mapsto B(g_1, \cdot)$. A biextension is an analogue to a categorified decurryfication of the map $A \mapsto \hat{A} = \operatorname{Hom}(A, B\mathbb{G}_m) \simeq \operatorname{Ext}^1(A, \mathbb{G}_m)$.

We first begin with some abstract definitions and results before moving to much more concrete formulas. Given some abelian groups $G_1, G_2, G_3$ (over some topos), a biextension $X$ of $G_1 \times G_2$ by $G_3$ is an element of the topos with projection maps $\pi_1, \pi_2$ to $G_1, G_2$ and an action of $G_3$ on $X$, such that for all $P_1 \in G_1$, $X_{P_1} := \pi_1^{-1}(P_1)$ is an extension of $G_2$ by $G_3$, and for all $P_2 \in G_2$, $X_{P_2} := \pi_2^{-1}(P_2)$ is an extension of $G_1$ by $G_3$. This defines two partial group structure $\star_2, \star_1$ on $\bar{X}$, and we further require that they satisfy some "obvious compatibility relations". The biextensions of $(G_1, G_2)$ by $G_3$ form a category $\operatorname{BiExt}(G_1, G_2; G_3)$.

More concretely, (working in the internal logic of the topos), an element $x \in X$ is said to be above $(g_1, g_2)$ if $\pi_i(x) = g_i$. All other elements $x'$ above $(g_1, g_2)$ are of the form $g_3 \cdot x$ for a unique $g_3 \in G_3$: they form a torsor under $G_3$. We will often use the notation $x_{g_1,g_2}$ to say that $x$ is above $(g_1, g_2)$. The biextension structure induces two partial group law. The first one $x_{g_1,g_2} \star_1 y_{g_1,g_2'} = z_{g_1+g_1',g_2}$ is valid whenever $\pi_2(x) = \pi_2(y)$. The second one $x_{g_1,g_2} \star_2 y_{g_1,g_2'} = z_{g_1,g_2+g_2'}$ is valid whenever $\pi_1(x) = \pi_1(y)$. The "obvious compatibility relations" requires that given $x_{g_1,g_2}, x_{g_1,g_2'}, x_{g_1',g_2}, x_{g_2',g_2'}$, we have

$$ (8) \quad (x_{g_1,g_2} \star_1 x_{g_1',g_2}) \star_2 (x_{g_1,g_2'} \star_1 x_{g_1,g_2'}) = (x_{g_1,g_2} \star_2 x_{g_1,g_2'}) \star_1 (x_{g_1',g_2} \star_2 x_{g_1',g_2}). $$

For an description of the compatibility relations Equation (8) as a commutative diagram in the external logic, see [Gro72, VII Définition 2.1].

We summarize the main results of [Gro72] on biextensions (which we state for completeness, we won't need to use these results, but instead we will rely on down to earth computations with explicit formulas). The functor $\operatorname{BiExt}$ is triadditive [Gro72, VII.(2.6.1)], covariant and cofibrant in $G_3$, and contravariant and fibrant in $G_1, G_2$ [Gro72, VII § 2], and left exact in each argument [Gro72, VII Proposition 3.7.6]. The category $\operatorname{BiExt}(G_1, G_2; G_3)$ is a stack [Gro72, VII § 2.8], whose homotopical invariants are given by $\operatorname{BiExt}(G_1, G_2; G_3)^0 := \pi_1(\operatorname{BiExt}(G_1, G_2; G_3)) = \text{group of endomorphisms of any biextension } X \simeq \operatorname{Hom}(G_1 \otimes G_2, G_3)$ [Gro72, VII § 2.5]; and furthermore $\operatorname{BiExt}(G_1, G_2; G_3)^1 := \pi_0(\operatorname{BiExt}(G_1, G_2; G_3))$, the set of isomorphism classes of biextensions, has a natural group structure defined in [Gro72, VII § 2.5] and such that $\operatorname{BiExt}(G_1, G_2; G_3)^1 \simeq \operatorname{Ext}^1(G_1 \otimes G_2, G_3)$ [Gro72, VII (3.6.5)]. This isomorphism is the main result of [Gro72, p. VII], and is used in [Gro72, p. VIII] to
define a pairing associated to a biextension [Gro72, VIII § 2]. This construction is extended in [Stao8, Theorem 17.1.1] to a Tate like pairing associated to a biextension.

Now we specialize these results to the case of abelian varieties (and then elliptic curves), where $G_1, G_2 = A, B$ are abelian varieties, and $G_3 = \mathbb{G}_m$ is the multiplicative group. This is the main case of interest of [Gro72, pp. VII, VIII], and Grothendieck proves:

**Theorem 3.1 (Grothendieck).** Let $A, B$ be abelian schemes. Then we have canonical isomorphisms (in the fppf topos) $\text{BiExt}(A, B; \mathbb{G}_m) \simeq \text{BiRigidifiedTorsors}(A, B; \mathbb{G}_m) \simeq \text{Correspondances}(A, B) \simeq \text{Hom}(A, \hat{B}) \simeq \text{Hom}(B, \hat{A})$.

Notably, given a morphism $f : A \to B$, there is a unique biextension $X_f$ associated to it, and if $f$ is an isogeny, the pairing associated to this biextension is the Weil-Cartier pairing $e_f$.

*Proof.* The first statement is [Gro72, VII Exemple 2.9.5 et Remarque 2.9.6], and the second is [Gro72, pp. VIII 2.3]. (It is stated to be the opposite of the Weil-Cartier pairing there, but there was a sign mistake corrected in [BBM79, § 5.1].) $\square$

**Example 3.2.** For instance, applying Theorem 3.1 to the identity morphism $A \to A$, we obtain the (birigidified) Poincaré line bundle and the Poincaré biextension.

Let $A$ be an abelian variety and $D$ be an ample divisor, and $\Phi_D : A \to \hat{A}$ be the associated polarisation. By Theorem 3.1, there is a unique biextension $X_D$ associated to $\Phi_D$ (which uniquely depends on the polarisation, hence on the algebraic equivalence class of $D$). Since $\hat{A} \simeq A$ by biduality, $X_D$ is a biextension of $A \times A$ by $\mathbb{G}_m$, and the corresponding birigidified torsor is the pullback of the Poincaré line bundle by $\text{Id} \times \Phi_D$, and suitably rigidified along $A \times 0$ and $0 \times A$.

**Remark 3.3.** The fact that the biextension pairing corresponds to the Weil-Cartier pairing for abelian schemes follows from abstract diagram chasings in [Gro72, pp. VIII 2.3]. A more elementary proof for elliptic curves is given by Stange in [Stao8, Theorem 17.1.2]; where it is also proven that her Tate like pairing associated to a biextension is indeed the usual Tate pairing for elliptic curves.

We will only need the unicity part of Theorem 3.1, and we will reprove below in Theorem 3.11 that the biextension pairings are the Weil and Tate pairings.

We have a canonical isomorphism $\iota : \text{BiExt}(G_1, G_2; G_3) \simeq \text{BiExt}(G_2, G_1; G_3)$ which consists in permuting the groups $G_1, G_2$ and the partial laws $\star_1, \star_2$. From the unicity part of Theorem 3.1 it follows that if $f : A \to B$ is a morphism of abelian schemes and $X_f$ the associated biextension, we have $\iota(X_f) = X_{\hat{f}}$. Now if we apply this to our polarisation $\Phi_D$, since it is autodual we obtain the following symmetry formula:

**Proposition 3.4.** Let $A$ be an abelian variety, $\Phi_D : A \to \hat{A}$ a polarisation associated to an ample divisor, and $X_D$ the associated biextension of $A \times A$ by $\mathbb{G}_m$. Then $X_D$ is symmetric: if $\iota(x_{a_1,a_2}) = \iota(x)_{a_2,a_1}$ denotes the same element seen above $(a_2, a_1)$ rather than $(a_1, a_2)$ (via the isomorphism $(a_1, a_2) \mapsto (a_2, a_1)$), then $x_{a_1,b} \star_1 x_{a_2,b} = \iota(x)_{b,a_1} \star_2 \iota(x)_{b,a_2}$.

*Proof.* The unicity argument above shows that the biextension laws are the same, up to a global automorphism of biextension. But a biextension of abelian varieties by $\mathbb{G}_m$ only has trivial automorphisms. $\square$

**Remark 3.5.** We even have the stronger statement that the biextension $X_D$ is symmetric in the sense of Breen [Bre83, § 1] (i.e. the symmetry above is compatible with the various natural structures on the biextension), owing to the fact that (the line bundle associated to
D) is a cubical torsor (see [Bre83, S 2] and [Mor85, Chapitre 1, § 2, 3]). We will come back to this in Section 4.

We are now ready to state explicit formulas for the biextension associated to a polarisation $\Phi_D$ on an abelian variety or an elliptic curve. Since the polarisation $\Phi_D$ depends only on the algebraic equivalence class of $D$ (which for an elliptic curve is determined by $\deg D$), for an elliptic curve we can assume that $D = D_n := n(0_E)$.

**Theorem 3.6.** Let $A$ be an abelian variety, $D$ a divisor, and $\Phi_D : A \to \hat{A}$ the associated morphism. The biextension $X_D$ of $A \times A$ by $\mathbb{G}_m$ associated to $D$ can be described as follows.

Its elements are tuples $(P, Q, g_{P,Q})$ such that the function $g_{P,Q}$ on $A$ has for divisor $t_P^*D_Q - D_Q = D_{P+Q} - D_P - D_Q$, where $D_Q = \Phi_D(Q) = t_Q^*D - D$. The projection $\pi : X_D \to A \times A$ sends $(P, Q, g_{P,Q})$ to $(P, Q)$. We will often drop $(P, Q)$ when referring to a biextension element $g_{P,Q} \in X_D$.

The divisors determine $g_{P,Q}$ up to some invertible constants, so the preimage of $\pi$ is indeed a torsor under $\mathbb{G}_m$. Since the divisor is invariant under permutation by $P, Q$, the function $g_{P,Q}$ can also be interpreted as an element $\iota(g)_{Q,P}$ above $(Q, P)$.

Fixing $Q$, the group law on $\pi_2^{-1}(Q)$ is equal to the group law (see Equations (1) and (6)) on the theta group $\mathcal{G}(D_Q)$. Fixing $P$, the group law on $\pi_1^{-1}(P)$ is equal to the one defined in Equation (7) via Equations (3) and (4).

Explicitly we have, if $g_{Q_1, Q_2}$ is any function with divisor $D_{Q_1+Q_2} - D_{Q_1} - D_{Q_2}$:

$$ (9) \qquad g_{P_1,Q} *_1 g_{P_2,Q} = g_{P_1+P_2,Q} := g_{P_1,Q}(\cdot)g_{P_2,Q}(\cdot + P_1)) $$

$$ (10) \qquad g_{P,Q_1} *_2 g_{P,Q_2} = g_{P,Q_1+Q_2} := g_{P,Q_1}(\cdot)g_{P,Q_2}(\cdot) \frac{g_{Q_1,Q_2}(\cdot + P)}{g_{Q_1,Q_2}(\cdot)}. $$

And since $X_D$ is a symmetric biextension:

$$ (11) \qquad g_{P_1,Q} *_1 g_{P_2,Q} = \iota(g)_{Q,P_1} *_2 \iota(g)_{Q,P_2'} $$

therefore we also have:

$$ g_{P_1,Q} *_1 g_{P_1,Q} = g_{P_1+P_2,Q} = g_{P_1,Q}(\cdot)g_{P_2,Q}(\cdot) \frac{g_{P_1,P_2}(\cdot + Q)}{g_{P_1,P_2}(\cdot)} $$

*Proof.* We saw in Section 2.3 that Equations (6) and (7) are still valid for an abelian variety.

We now check that the formulas in Theorem 3.6 define a structure of biextension on $X_n$. By definition of the theta groups, the group structures on $\pi_1^{-1}(P)$ and $\pi_2^{-1}(Q)$ we use do give extensions of $A$ by $\mathbb{G}_m$ as expected. An immediate computation also shows that the partial laws $*_1,*_2$ satisfy the compatibility relations of Equation (8), so $X_D$ is a biextension.

By Theorem 3.1, $X_D$ is the biextension associated to some morphism $\Phi : A \to \hat{A}$. We let to the reader the fun diagram chasing exercise to unravel the definitions of [Gro72, p. VII] and check that this $\Phi$ is the polarisation $\Phi_D$ we started with. (This diagram chasing becomes easier when using the fact that the symmetric biextension $X_D$ is associated to the explicit cubical structure on (the line bundle associated to) $D$, see [Bre83; Mor85, Chapitre 1]. Alternatively, it is shown in [Gro72, VIII § 2] that the pairing associated to the biextension associated to $\Phi$ is the Weil pairing associated to $\Phi$, and we will see in Theorem 3.11 that the pairing associated to our $X_D$ is $\Phi_D$, so $\Phi = \Phi_D$.)

Equation (11) follows from Proposition 3.4. $\square$

<figure><img src="image_2.png" /></figure>
**Example 3.7.** The inversion $g_{P,Q}^{*1,-1}$ is given by

$$g_{-P,Q} = \frac{1}{g_{P,Q} g_{P,-P}(\cdot + Q)}.$$

**Remark 3.8.** The biextension $X_D$ only depends on the polarisation $\Phi_D$, so if $D$ is ample only on its algebraic equivalence class. Explicit isomorphisms can be given as follows: if $D_1 \sim D_2$ and $\alpha$ is any function with divisor $D_2 - D_1$, then $t_Q^*\alpha/\alpha$ has for divisor $D_{2,Q} - D_{1,Q}$ hence by Equation (4) the isomorphism is given by

$$(P, g_{P,Q}) \in G(D_{1,Q}) \subset X_{D_1} \mapsto (P, g_P(\cdot) \frac{\alpha(\cdot + P + Q)\alpha(\cdot)}{\alpha(\cdot + P)\alpha(\cdot + Q)}) \in G(D_{2,Q}) \subset X_{D_2}.$$

And if $D_2 = t_c^*D_1$, then $D_{2,Q} = t_c^*D_{1,Q}$ so by Equation (5) the isomorphism is:

$$(P, g_{P,Q}) \in G(D_{1,Q}) \subset X_{D_1} \mapsto (P, t_c^*g_P) \in G(D_{2,Q}) \subset X_{D_2}.$$

**3.2. Monodromy and pairings in biextensions.** In Section 2, we saw how the exponentiation in theta groups $G(D_Q)$ naturally gave rise to the Weil and Tate pairings on an elliptic curve $E$ or abelian variety, but we often had to juggle and switch between different theta groups. In Section 3 and Theorem 3.6, we saw that the biextension $X$ associated to the divisor $(0_E)$ is a convenient way to package all the theta groups $G(D_Q)$ together. We will now, following [Gro72, p. VIII] and [Sta08, Theorem 17.1.1], reinterpret the Weil and Tate pairings as monodromy information on the biextension.

We first look at the case of an elliptic curve $E$. The monodromy is as follows: let $P \in E[\ell]$ and $g_{P,Q} \in X$ be an element in the biextension associated to $(0_E)$, $g_{P,Q}$ is a function with divisor $D_{P+Q} - D_P - D_Q = (-P - Q) + (0_E) - (-P) - (-Q) -$ by Theorem 3.6. Since $\ell P = 0_E$, we have $g_{P,Q}^{*1,\ell}$ is an element above $(0_E, Q)$, so a function with trivial divisor, so a constant $\lambda_P$. However, even through $P$ is of order $\ell$, $g_{P,Q}$ need not be, so we may have $\lambda_P \neq 1$. We do have $g_{P,Q}^{*1,\ell m} = \lambda_P^m$, so if $k = \mathbb{F}_q$ is a finite field and $g_{P,Q}$ is rational, $g_{P,Q}$ is at most of order $\ell(q-1)$. We call $\lambda_P$ the monodromy associated to $g_{P,Q}$ (beware of the notation, it also depends on $Q$).

We remark that changing $g_{P,Q}$ to $\mu g_{P,Q}$, we have $(\mu g_{P,Q})^{*1,\ell} = \mu^\ell \lambda_P$, so the class of $\lambda_P$ in $k^*/k^{*,\ell}$ only depends on $(P, Q)$, not on $g_{P,Q}$. Also, if $k = \mathbb{F}_q$ and $\ell | q-1$, $\lambda_P^{(q-1)/\ell} = g_{P,Q}^{*1,q-1}$ is a $\ell$-th root of unity which does not depend on the choice of the (rational) $g_{P,Q}$ but only on $(P, Q)$.

As expected, this monodromy $\lambda_P$ will give pairings. We will also see in Section 3.4 how the Ate and optimal Ate pairings can also be interpreted as monodromy associated to endomorphisms of the form $\sum c_i \pi_q^i$.

In this article, we will need to be able to compute pairings associated with non principal polarisation. Reusing the notations of Section 2.3, if $D$ is a divisor on $A$, $X_D$ the associated biextension, and $g_{P,Q} \in X_D$ where $P \in A[\ell D]$, we may not have $\ell P = 0$, so $g_{P,Q}^\ell$ may not be a constant. We had the same problem for Theorem 2.9, and we will use the same solution.

Recall that a biextension element $g_{P,Q}$ has for divisor $D_{P+Q} + D_0 - D_P - D_Q$, which is principal because it is associated to the cycle $(P+Q) + (0) - (P) - (0)$ (with our conventions $D_0 = 0$ so we often omit it). But when $P \in A[D]$, $D_P$ is already principal, so we may take an associated function $g_P$ (we remark that $(P, g_P)$ is an element of the theta group $G(D)$). The function $g_P(\cdot + Q)/g_P$ has for divisor $D_{P+Q} - D_P - D_Q$, so is an element of $X_D$ above $(P, Q)$. We remark that it does not depend on our choice of $g_P$.
**Lemma 3.9.** Fix $Q \in A$. We let $(X_{D,Q}, \star_1)$ be the group of all biextension elements above $(P', Q)$ for some $P'$. The map $s_Q : A[D] \to X_{D,Q}$, $P \mapsto s_{P,Q} := g_P(\cdot + Q)/g_P$ is a group morphism. This induces a group action $P \cdot g_{P',Q} := s_Q(P) \star_1 g_{P',Q}$ of $A[D]$ on $X_D$.

**Proof.** $\frac{g_{P_1}(\cdot+Q)}{g_{P_1}} \star_1 g_{P_2}(\cdot+Q) g_{P_2} = \frac{g_{P_1}(\cdot+Q) g_{P_2}(\cdot+P_1+Q)}{g_{P_1} g_{P_2}(\cdot+P_1)} = \frac{g_{P_1+P_2}(\cdot+Q)}{g_{P_1+P_2}}$ where $g_{P_1+P_2} = g_{P_1} g_{P_2} (\cdot+P_1)$ is the element of $G(D)$ above $P_1+P_2$ coming from the composition $(P_1, g_{P_1}) \cdot (P_2, g_{P_2})$. $\square$

By Theorem 3.6, the reformulation of Porism 2.10 in terms of biextension is:

**Porism 3.10.** Let $g_{P,Q} \in X_D$ and let $g_{\ell P,Q} = g_{P,Q}^{\star_1, \ell}$. Then the function $f_{\ell,P}$ evaluated on the cycle $(x+Q) - (x)$ is given by $\frac{g_{\ell P,Q}}{g_{P,Q}^{\ell}}$.

If furthermore $P \in A[\ell D], f_{-\ell D_P}((R+Q)-(R)) = \frac{(-\ell P) \cdot g_{\ell P,Q}}{g_{P,Q}^{\ell}}(R)$.

**Theorem 3.11 (Monodromy pairings).** Let $X_D$ be the biextension associated to a divisor $D$ on an abelian variety $A$. Let $(P, Q, g_{P,Q}) \in X_D$ be a biextension element above $(P, Q)$. If $P \in A[\ell D]$, we let $g_{\ell P,Q} = g_{P,Q}^{\star_1, \ell}$ is above $(\ell P, Q)$. Furthermore, $\ell P \in A[D]$, so by Lemma 3.9 there is a canonical biextension element $(\ell P, Q, s_{\ell P,Q})$ above $(\ell P, Q)$. The element $g_{\ell P,Q} \star_1 s_{\ell P,Q}^{\star_1, -1} = g_{\ell P,Q} \star_1 s_{-\ell P,Q} = (-\ell P) \cdot g_{\ell P,Q}$ is above $(0, Q)$ so is a constant $\lambda_P$. We say that $\lambda_P$ is the $\ell$-monodromy associated to $(P, Q, g_{P,Q})$.

If $Q \in A[\ell D]$, the Weil pairing is given (up to a sign) by: $e_{W,D,\ell}(P, Q) = \lambda_P/\lambda_Q$

If $P \in A[\ell D](k)$, and $(P, Q, g_{P,Q}) \in X_D(k)$, i.e. $g_{P,Q}$ is chosen to be rational, then the non reduced Tate pairing is given by: $e_{T,D,\ell}(P, Q) = \lambda_P$.

**Proof.** This is a translation of Theorem 2.9 in terms of the biextension formulas from Theorem 3.6. $\square$

The exact same remark as in Remark 2.11 applies for the extended Tate pairing computed through biextensions. If $D = mD_1$ with $D_1$ associated to a principal polarisation, and $P \in A[mD_1]$, and we want to compute the Tate pairing as an element of $k^*/k^{*,\ell m}$, we need to keep track of the function $g_{P,Q}^{\ell}$. There is a tensor map $X_{D_1} \to X_D$, $g_{P,Q} \mapsto g_{P,Q}^m$, and if our starting biextension element $g_{P,Q}$ is in the image of this map (on a rational element), then $g_{P,Q}^{\ell}(x)$ lies in $k^*, \ell m$ for $x$ rational so we can express the extended Tate pairing purely in terms of the monodromy $\lambda_P$. But we stress that one needs to be careful that, starting with a general biextension element $g_{P,Q}$ (which won't be a $m$-fold tensor in general), we cannot compute the Tate pairing for $\ell mD_1$ while working on the biextension $X_D$ purely from monodromy information, we need to keep track of a corrective factor.

**Corollary 3.12.** Let $X_\Theta$ be the biextension associated to an ample divisor $\Theta$ on an abelian variety $A$.

Fix any biextension element $(P, Q, g_{P,Q})$ above $P, Q$, we can also see it as an element of the group $(X_\Theta, Q, \star_1)$. If $P \in A[\ell]$, the exponentiation $g_{P,Q}^{\star_1, \ell}$ is a constant $\lambda_P$, which is the $\ell$-monodromy associated to $(P, Q, g_{P,Q})$. Alternatively, we have $g_{P,Q}^{\star_1, \ell+1} = \lambda_P g_{P,Q}$.

If $P, Q \in A[\ell]$, the Weil pairing $e_{W,\Theta,\ell}$ is (up to a sign) $\lambda_P/\lambda_Q$. If $P \in A[\ell](k)$, assuming that $g_{P,Q}$ is rational, the non reduced Tate pairing is (up to a sign) $e_{T,\Theta,\ell} = \lambda_P$. If $k = \mathbb{F}_q$ is a finite field and $\mu_\ell \subset \mathbb{F}_q$, we can also define $\lambda'_P$ as the constant $g_{P,Q}^{\star_1, q-1}$. Alternatively, we have $g_{P,Q}^{\star_1, q} = \lambda'_P g_{P,Q}$. Then the reduced Tate pairing is (up to a sign) is given by $\lambda'_P$.
*Proof.* This is a direct application of Theorem 3.11, using the fact that if $\ell P = 0$, $s_{0,Q} = 1$. See also Corollary 2.5. $\square$

**Remark 3.13.** Let $g_{P,Q}$ be as in Corollary 3.12, and $\lambda_P$ the monodromy: $g_{P,Q}^{*1,\ell} = \lambda_P$. Then if $n_2 = m\ell + n_1, n_1, n_2, m \in \mathbb{Z}$, then $g_{P,Q}^{*1,n_2} = \lambda_P^m g_{P,Q}^{*1,n_1}$. In particular, we have $g_{P,Q}^{*1,\ell+1} = \lambda_P g_{P,Q}$ and $g_{P,Q}^{*1,\ell-1} = \lambda_P g_{P,Q}^{*1,-1}$. Sometimes, it is easier to compute the monodromy $\lambda_P$ using these relations.

**Remark 3.14 (Refined bilinearity for the Tate pairing).** The (non reduced) Tate pairing is only bilinear when we consider its value in $k^*/k^{*,\ell}$. However, by Remark 3.13 we have a refined version of bilinearity: assume we take $g_{P,Q}$ to compute the Tate pairing $e_\ell(P, Q)$ via the monodromy relation $g_{P,Q}^{*1,\ell} = \lambda_P \in k^*$.

Now assume that to compute the Tate pairing $e_\ell(iP, Q)$, we take $g_{iP,Q} = g_{P,Q}^{*1,i}$ rather than an arbitrary element. Then we have $g_{iP,Q}^{*1,\ell} = g_{P,Q}^{*1,i\ell} = \lambda_P^i \in k^*$.

Likewise, for the Tate pairing $e_\ell(P, iQ)$, if we take $g_{P,iQ} = g_{P,Q}^{*2,i}$, we have $g_{P,iQ}^{*1,\ell} = (g_{P,Q}^{*1,\ell})^{*2,i} = \lambda_P^i \in k^*$ by the compatibility between $\star_1$ and $\star_2$.

Of course, there is a priori no canonical choice of $g_{iP,Q}$ for all $i$, depending only on $iP$, such that $g_{iP,Q} = g_{P,Q}^{*1,i}$ (at least without computing a DLP of $iP$ with respect to $P$), so no way to exploit this refined bilinearity. But see Remark 4.20 for a partial choice.

**3.3. The arithmetic of biextensions on elliptic curves: the evaluation representation.** To exploit Theorem 3.11 for computing the Weil and Tate pairings, we need to develop efficient arithmetic on biextensions. In particular, by Corollary 3.12, to compute the polarised Weil and Tate pairing efficiently on an abelian variety $(A, \Theta)$, we need a fast exponentiation in the group $(X_{\Theta,Q}, \star_1)$ induced by the biextension $X_{\Theta}$. In particular we can apply all well known techniques for group exponentiation: double and add, windowing, slidings windows, NAF, combings...These tools are of course well known in the pairing literature. But beware that the context is different for pairings than for scalar multiplication: in the ECC context, the same base point $P$ is multiplied by different scalars, whereas in the pairing context different biextension elements $g_{P,Q}$ are multiplied by the same scalar $\ell$.

For simplicity, we go back to the case of elliptic curves, but as usual everything holds for general abelian varieties. It remains to do the basic group operations, using $\star_1$ or $\star_2$ since it gives the same result by Proposition 3.4. For an elliptic curve $E$, taking $D = (0_E)$ the canonical principal polarisation, an element $g_{P,Q}$ of the biextension $X_{0_E}$, since it is a function with divisor $D_{P+Q} - D_P - D_Q = (-P - Q) + (0) - (-P) - (-Q)$ is (in the generic case) of the form

$$ (12) \qquad g_{P,Q}(x,y) = c \frac{x - x_{P+Q}}{y - y_P - \alpha(x - x_P)} $$

where $\alpha$ is the slope of the line $l_{P,Q}$ going through $P$ and $Q$. To compute the biextension law $g_{P_1,Q} \star_1 g_{P_2,Q}$ it suffices to plug in the formula Equation (10) (using the elliptic group law), and then reduce modulo the elliptic curve equation to obtain an equation of $g_{P_1+P_2,Q}$ of the form above. However, this is not very efficient. We will instead try to find a more efficient representation of biextension elements.

First, we remark that $g_{P,Q}$ is completely determined, up to a constant, from $(P, Q)$ (which gives its divisor $D_{P+Q} - D_P - D_Q$. Using the full function form of $g_{P,Q}$ to determine this function is thus overkill; a more efficient representation is to simply use its evaluation
$g_{P,Q}(R_0)$ at some base point $R_0$. The biextension element is then represented by $(P, Q, c := g_{P,Q}(R_0))$, we call this the evaluation representation.

Note that if $R_0$ is a pole or zero of $R_0$, we can use the standard trick of fixing a uniformiser $\pi_{R_0}$ at $R_0$, and “defining” $g_{P,Q}(R_0)$ to be the first coefficient of the Laurent series expansion of $g_{P,Q}$ along $\pi_{R_0}$ (we called this the extended value of Remark 2.8).

It is customary to take $R_0 = 0_E$; if

$$ \mu_{P,Q}(x,y) = \frac{x - x_{P+Q}}{y - y_P - \alpha(x - x_P)} $$

is the “usual” (recall that we use a somewhat non standard sign convention, see Remark 2.2) normalised Miller function with divisor $(-P-Q) + (0_E) - (-P) - (-Q)$ and $g_{P,Q}$ is as in Equation (12), then $g_{P,Q} = c\mu_{P,Q}$ so $g_{P,Q}(0_E) = c$ (the extended value for the uniformiser $\pi_{0_E} = x/y$).

The biextension formulas (using either law $\star = \star_1, \star_2$) then gives:

$$ (13) \qquad (P_1, Q, c_1) \star (P_2, Q, c_2) = c_1 c_2 \frac{g_{P_1, P_2}(R_0 + Q)}{g_{P_1, P_2}(R_0)} $$

from which it follows that

$$ (14) \qquad g_{P,Q}^{\star_1, \ell} = g_{P,Q}(R_0)^{\ell} f_{\ell,P}((R_0 + Q) - (R_0)) $$

where $\text{div} f_{\ell,P} = D_{\ell P} - \ell D_P = (-\ell P) + (\ell - 1)(0_E) - \ell(P)$.

Thus, the biextension arithmetic and exponentiation in the evaluation representation gives exactly the usual Miller algorithm, modulo our different sign conventions.

Going through all the theory of biextensions only to recover the standard Miller algorithm might seem overkill. We will be rewarded in later sections when using other biextension representations.

There are still some useful information we can glean from the biextension interpretation of Miller's algorithm. First, as mentioned above, it is well known in the pairing literature that Miller's formula forms a group law, to which we can apply the standard group exponentiation algorithms. The biextension gives a geometric interpretation of this group law. In particular, it gives a geometric interpretation of the various relations on the functions $f_{\ell,P}$ used to define the ate and optimal ate pairings (we will go back to this in Section 3.4). For instance, by Corollary 3.12 the reduced Tate pairing is given by $f_{q-1,P}((R_0 + Q) - (R_0))$; of course since the field arithmetic is faster than the biextension arithmetic, it is more efficient to first compute the reduced Tate pairing via $f_{\ell,P}((R_0 + Q) - (R_0))$ and then proceed via the final exponentiation by field arithmetic (equivalently: working on the biextension over $(0, Q)$).

Secondly, it shows that the values $f_{\ell,P}((R_0 + Q) - (R_0))$ we compute during Miller's algorithm are simply a convenient representations of the functions $g_{\ell P,Q}$ coming from the biextension. During the execution of Miller's algorithm, it can happen that we need to evaluate our intermediate Miller functions on a pole or zero. The standard solution is to use a uniformiser, explicit formulas are given in [Rob21a, Lemma 3.5.3]. Another solution is to change the evaluation point $R_0$ to a new point $R'_0$. But rather than restarting Miller's algorithm from scratch, we can change the evaluation point on the fly, by going from the evaluation representation on $R_0$ back to the function representation back to the evaluation representation on $R'_0$. Explicitly, if we have the representation $(P, Q, g_{P,Q}(R_0))$, we can compute any function (eg the normalised one) $\mu_{P,Q}$ with divisor $D_{P+Q} - D_P - D_Q$, and then use $g_{P,Q}(R'_0) = \mu_{P,Q}(R'_0)g_{P,Q}(R_0)/\mu_{P,Q}(R_0)$.

Thirdly, the symmetry relation $g_{P_1,Q} \star_1 g_{P_2,Q} = g_{Q,P_1} \star_2 g_{Q,P_2}$ from Proposition 3.4 gives the following relation on the normalised functions $\mu_{P,Q}$:
**Lemma 3.15.** $\mu_{P_1,P_2}(P_3) = \mu_{P_2,P_3}(P_1) = \mu_{P_3,P_1}(P_2)$.

*Proof.* By Theorem 3.6, we have $\mu_{P_1,Q} *_1 \mu_{P_2,Q} = \mu_{P_1,Q}(\cdot)\mu_{P_2,Q}(\cdot + P_1))$, while $\mu_{P,Q_1} *_2 \mu_{P_2,Q} = \mu_{P_1,Q}(\cdot)\mu_{P_2,Q}(\cdot)\frac{\mu_{P_1,P_2}(\cdot+Q)}{\mu_{P_1,P_2}(\cdot)}$. It follows that $\mu_{P_2,Q}\mu_{P_1,P_2}(\cdot + Q) = \mu_{P_2,Q}(\cdot + P_1)\mu_{P_1,P_2}$. Evaluating this equaliting on $0_E$ (multiplying both members by the appropriate uniformiser to that the evaluation is well defined) gives $\mu_{P_1,P_2}(Q) = \mu_{P_2,Q}(P_1)$, from which the lemma follows by a change of variable. $\square$

**Remark 3.16.** Recall from Remark 2.2 that we use a different sign convention than usual.

In this remark only, we go back to the standard sign convention, and let $\mu_{P,Q}$ be the standard normalised Miller function with divisor $(P) + (Q) - (P + Q) - (0_E)$, and $f_{\ell,P}$ the standard normalised Miller function with divisor $\ell(P) - (\ell P) - (\ell - 1)(0_E)$. Then Lemma 3.15 becomes on these standard functions: $\mu_{P_1,P_2}(-P_3) = \mu_{P_2,P_3}(-P_1) = \mu_{P_3,P_1}(-P_2)$.

We leave as an exercise to the reader to prove this fact (and its generalisation to abelian varieties) without the theory of biextensions.

This gives the following interesting tweaks on Miller's algorithm: for the Miller addition, we have $f_{\ell+1,P}(Q) = f_{\ell,P}(Q)\mu_{\ell,P}(Q) = f_{\ell,P}(Q)\mu_{P,-Q}(-\ell P)$. In other words, rather than evaluating the different Miller functions $\mu_{\ell,P,P}$ on the same point, we could evaluate the same (precomputed) Miller function $\mu_{P,-Q}$ on the different points $-\ell P$.

Likewise, for the Miller doubling: $f_{\ell+\ell,P}(Q) = f_{\ell,P}(Q)^2\mu_{\ell,P,P}(Q) = f_{\ell,P}(Q)^2\mu_{\ell,P,-Q}(-\ell P)$. The numerator of $\mu_{\ell,P,-Q}$ is $y - y(\ell P) - \alpha(x - x(\ell P))$, which evaluated on $-\ell P$ is given by the simple formula $-2y(\ell P)$. However, the evaluated denominator is $x(\ell P) - x(\ell P - Q)$, which requires to compute $\ell P - Q$. This will be a recurring theme in our latter algorithm than in our pairing algorithms we will compute arithmetic informations both from $\ell P$ and $\pm Q + \ell P$.

We remark that faster formulas for the standard Miller's algorithm have been obtained by slightly tweaking the Miller functions. In [DZZZ22] the authors introduce functions with divisors $\ell(P) + (-\ell P) - (\ell + 1)(0)$ which give a streamlined double and add formula. In [BELL10], the following formula is used: $f_{\ell_1+\ell_2,P} = \frac{1}{f_{-\ell_1,P}f_{-\ell_2,P}l_{-\ell_1,P,-\ell_2,P}}$, instead of the standard formula: $f_{\ell_1+\ell_2,P} = f_{\ell_1,P}f_{\ell_2,P}\mu_{\ell_1,P,\ell_2,P}$. We let open the question of whether combining these tweaks with Lemma 3.15 could give further speed ups.

**3.4. The Ate and optimal Ate pairings as monodromy pairings.** We also can give a monodromy interpretation of the Ate pairing.

If $X_D$ is a biextension associated to an abelian variety $(A, D)$ over a field $k$, and $k/k_0$ is a Galoisian extension, the Galoisian action can be described as follows. Let $(P, Q, g_{P,Q}) \in X_D$ and $\sigma \in \text{Gal}(k/k_0)$, then $\sigma(P, Q, g_{P,Q}) = (\sigma(P), \sigma(Q), g_{P,Q}^{\sigma})$ where $g_{P,Q}^{\sigma}$ is the function with divisor $D_{\sigma(P+Q)} - D_{\sigma(P)} - D_{\sigma(Q)}$ such that $g_{P,Q}^{\sigma}(\sigma(R)) = \sigma(g_{P,Q}(R))$.

Now assume for simplicity that $(A, D)$ is an elliptic curve $(E, (0_E))$ over a finite field $\mathbb{F}_q$; as usual our formulas will still be valid for a general abelian variety over $\mathbb{F}_q$ (for a definition of the Ate and optimal Ate pairings for abelian varieties, see [LR15]). For the Ate pairing situation, we assume that $E[\ell](\mathbb{F}_q)$ is not empty but that the embedding degree $d$ is greater than 1, thus the full $\ell$-torsion is defined over $\mathbb{F}_{q^d}$, and $E[\ell] = \mathbb{G}_1 \oplus \mathbb{G}_2$ where $\mathbb{G}_1 = E[\ell](\mathbb{F}_q)$ is the eigenspace of $\pi_q$ for its eigenvalue 1, and $\mathbb{G}_2 = \{Q \in E[\ell](\mathbb{F}_q) | \pi_q Q = qQ\}$ is the eigenspace for the eigenvalue $q$.

In pairing based cryptography, we consider the (non reduced) Tate pairing as restricted to $\mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{F}_{q^d}^*/\mathbb{F}_{q^d}^{*,\ell}$, while the (reduced) Ate pairing $a_{\lambda,\ell}: \mathbb{G}_2 \times \mathbb{G}_1 \to \mathbb{F}_{q^d}^*/\mathbb{F}_{q^d}^{*,\ell}$ is given by $a_{\lambda,\ell}(P,Q) = f_{\lambda,P}((Q) - (0))$ for any $\lambda \equiv q \bmod \ell$. In the special case when
$\lambda = q$, the Ate pairing $a_{T,q}$ is already reduced, otherwise the reduced Ate pairing is given by $f_{\lambda,p}((Q) - (0))^{(q^d-1)/\ell} \in \mu_\ell$.

Now let $g = (P, Q, g_{P,Q})$ be a biextension element with $P \in \mathbb{G}_2$ and $Q \in \mathbb{G}_1$. Then $\pi_q(g) = (qP, Q, g_{P,Q}^{\pi_q})$ and $g^{*1,\lambda}$ are both biextension elements above $(qP, Q)$. They need not be equal, and in fact the monodromy between them is precisely the $\lambda$-Ate pairing.

**Proposition 3.17.** Let $P \in \mathbb{G}_2$, $Q \in \mathbb{G}_1$, $g_{P,Q}$ any biextension element in $\mathbb{F}_{q^d}$ above $(P, Q)$, and let $c$ be the monodromy such that $g_{P,Q}^{*1,\lambda} = c\pi_q(g_{P,Q})$. Then $c$ gives the $\lambda$-Ate pairing: $a_{\lambda,\ell}(P, Q) = c$.

*Proof.* Immediate from the definitions and Porism 3.10. $\square$

<figure><img src="image_3.png" /></figure>

**Remark 3.18 (Optimal Ate).** Write $\ell = \sum c_i q^i$. Then rather than computing $g_{P,Q}^{*1,\ell}$ as $\prod_{*1,i} (g_{P,Q}^{*1,c_i})^{*1,q^i} = e_{T,\ell}(P, Q)$ (the non reduced Tate pairing), we can compute $\prod_{*1,i} (\pi_q^i)(g_{P,Q}^{*1,c_i}) = C$. By Proposition 3.17, this will differ from the Tate pairing by a bunch of Ate pairings; and by Porism 3.10 this is exactly the optimal Ate pairing.

We leave to the reader the monodromy interpretation of the twisted Ate and the Eil pairing when given an automorphism $\alpha$ of order dividing $d$.

**Corollary 3.19 (Explicit formulas).** Using the evaluation representation $(P, Q, g_{P,Q}(R_0))$ of biextension elements, the Ate pairing on $\mathbb{G}_2 \times \mathbb{G}_1$ is computed as follows: if $g_{P,Q}$ is represented by $(P, Q, c)$, and $g_{P,Q}^{*1,\lambda} = (qP, Q, c')$ then $a_{\lambda,\ell}(P, Q) = c'/c^q$.

If $\ell = \sum a_i q^i$, and $g_{P,Q}^{*1,a_i} = (a_i P, Q, c_i)$, then the optimal Ate pairing is given by the constant $\prod_{*1,i} (q^i a_i P, Q, c_i^{q^i})$.

**Remark 3.20 (The reduced Ate and Tate pairings).** When computing the $\lambda$-ate pairing, changing the representative $g_{P,Q}$ by $u \cdot g_{P,Q}$ for some $u \in \bar{\mathbb{F}}_q^*$ changes the value of the $\lambda$-Ate pairing by $g_{P,Q}^{*1,\lambda} / \pi_q(g_{P,Q}) = u^{\lambda-q}$. Hence we recover the fact that the $q$-Ate pairing is already reduced, and does not depends on the choice of representative.

As an aside, since $\mu_\ell \subset \mathbb{F}_{q^d}$, we saw that the reduced Tate pairing was given by $g_{P,Q}^{*1,q^d} / g_{P,Q}$ for any $g_{P,Q}$ defined over $\mathbb{F}_{q^d}$. The true definition of the reduced Tate pairing should actually be as the monodromy $g_{P,Q}^{*1,q^d} / \pi_{q^d}(g_{P,Q})$. In this case, it does not depends on the choice of representative for $g_{P,Q}$ either, even a non rational one, and reduces to the definition given above when $g_{P,Q}$ is defined over $\mathbb{F}_{q^d}$.

**Remark 3.21 (The Ate and Tate pairings as Weil-Cartier pairings).** It is well known that the reduced Tate pairing $e_{T,\ell}(P, Q)$ is induced by the Weil-Cartier pairing $e_{\pi_q^{d-1}} : E[\pi_q^d - 1] \times E[\pi_q^{d-1}] \to \mathbb{G}_m$. Furthermore, $\pi_q^d = \pi_q^d$ when restricted to $E[\ell]$, by definition of the embedding degree.

It is maybe less known, but the $q$-Ate pairing can also be interpreted as a Weil-Cartier pairing:

$$ (15) \qquad a_{q,\ell}(P,Q) = e_{\pi_q-1}(P,Q)^q = e_{\pi_q-1}(P,qQ) = e_{\pi_q-1}(\pi_q P, \pi_q Q). $$

We remark that by definition, $\mathbb{G}_1 \subset \text{Ker } \pi_q - 1$ and $\mathbb{G}_2 \subset \text{Ker } \hat{\pi}_q - 1$. Equation (15) can be proven using the relationship between the Ate and Tate pairings (see [Ver10]), and the relationship between the Weil-Cartier pairings of $\pi_q - 1$ and $\pi_q^d - 1 = (\pi_q - 1)(1 + \cdots + \pi_q^{d-1})$ coming from the compatibility of the Weil-Cartier pairings with isogenies.
We will use this to give a monodromy interpretation of the Weil-Cartier pairing associated to $\pi_q^d - 1$ and $\pi_q - 1$.

First as a warm-up, let us recall the monodromy interpretation of the Weil pairing: we take $P, Q \in E[\ell]$, a $g_{P,Q}$ in the biextension above them, and compute the monodromy $g_{P,Q}^{*1,\ell} = c_1 \cdot g_{P,Q}, g_{P,Q}^{*2,\ell} = c_2 \cdot g_{P,Q}$ to get the Weil pairing $e_{W,\ell}(P,Q) = c_1/c_2$. An alternative way is to compute the monodromy $(g_{P,Q}^{*1,\ell})^{*2,\ell} = c(g_{P,Q}^{*2,\ell})^{*1,\ell}$, a quick calculation gives $c = c_1/c_2(c_2/c_1)^\ell = c_1/c_2$ (using that $e_{W,\ell}(P,Q) \in \mu_\ell$) so this also gives the Weil pairing (and we recover the commutator interpretation of Example 2.1).

For the $\alpha$-Weil-Cartier pairing, $\alpha$ an endomorphism, to compute $e_\alpha(P, Q)$ when $P \in$ Ker $\alpha$ and $Q \in$ Ker $\hat{\alpha}$, it is natural to see if a possible strategy to compute $e_\alpha$ is to take the quotient of the monodromy of the action of $\alpha$ on $g_{P,Q}$ (any biextension element above $(P, Q)$) with respect to $\star_1$, and the action of $\hat{\alpha}$ on $g_{P,Q}$ with respect to $\star_2$. Using Proposition 3.17 and the interpretation of the reduced Tate and Ate pairings as Weil-Cartier pairings above, we'll see that an analogous strategy does hold for $\alpha = \pi_q - 1$ and $\alpha = \pi_q^d - 1$.

We first start with the Weil-Cartier pairing for $\pi_q^d - 1$. We first want to compute the action of $\pi_q^d - 1$ on $g_{P,Q}$ with respect to $\star_1$ and compare it with 1; it will be easier to compute $\pi_q^d$ on $g_{P,Q}$ and compare it with $g_{P,Q}: \pi_q^d(g_{P,Q}) = c_1 \cdot g_{P,Q}$. Likewise, rather than computing the action of $\hat{\pi}_q^d - 1$ on $g_{P,Q}$ with respect to $\star_2$ and compare it with 1, we will compute the action of $\hat{\pi}_q^d$ on $g_{P,Q}$ and compare it with $g_{P,Q}$. Now $\hat{\pi}_q^d = q^d \pi_q^{-d}$. We have $\pi_q^{-d}(g_{P,Q}) = 1/\pi_q^{-d}(c_1) \cdot g_{P,Q}$, and $(q^d \pi_q^{-d}) \cdot \star_2 (g_{P,Q}) = (1/\pi_q^{-d}(c_1)) q^d g_{P,Q}^{\star_2 q^d} = 1/c_1 g_{P,Q}^{\star_2 q^d}$. So the monodromy quotient is given by $g_{P,Q}^{\star_2 q^d} / \pi_q^d(g_{P,Q})$ which is precisely the formula from Remark 3.20 for the reduced Tate pairing. Hence we do have a correct formula for the Weil-Cartier pairing of $\pi_q^d - 1$.

Now we try to find a monodromy approach to compute the Weil-Cartier pairing for $\pi_q - 1$ on $\pi_q(P), \pi_q(Q)$, with $\pi_q(P) \in \mathbb{G}_1, \pi_q(Q) \in \mathbb{G}_2$ (beware that we switched arguments compared to Proposition 3.17). We can assume that we are given an element of the form $g_{\pi(P),\pi(Q)} = \pi_q(g_{P,Q})$ above $(\pi_q(P), \pi_q(Q))$. We want to first compute the quotient of the action (with respect to $\star_2$) of $\hat{\pi}_q = q\pi_q^{-1}$ on $\pi_q(g_{P,Q})$ and $\pi_q(g_{P,Q})$. By the same computation as above, the result is precisely the monodromy $g_{P,Q}^{\star_2 q^d}/\pi_q(g_{P,Q})$, i.e., the $q$-Ate pairing (using the symmetry $\star_2 = \star_1$ and the fact that we switched the side of the arguments). Strangely, in this case we do not need to compute a monodromy action of $\pi_q$ on $g_{\pi(P),\pi(Q)}$ with respect to $\star_1$ and compare it to $g_{\pi(P),\pi(Q)}$.

**Remark 3.22** (Twists and automorphisms). Let $\psi : A' \to A$ be an isomorphism, and let $D' = \psi^*D$. Then we have an isomorphism of biextensions $X_D \to X_{D'}$, $g_{P,Q} \mapsto \psi^*g_{P,Q} = g_{P,Q} \circ \psi = g_{P',Q'}$ where $P' = \psi^{-1}(P)$ and $Q' = \psi^{-1}(Q)$.

In particular, any monodromy information computed from $g_{P,Q}$ via the biextension arithmetic on $X_D$, can also be recovered via $g_{P',Q'}$ and the biextension arithmetic on $X_{D'}$. This generalises [CLN10] to abelian varieties.

Indeed, in that article, the authors explain that if $E/\mathbb{F}_q$ is an elliptic curve admitting a twist of degree $f$, and we want to do pairings over $E/\mathbb{F}_{q^d}$ with $f|d$, then we can consider the twist $E'/\mathbb{F}_{q^{d/f}}$ of $E/\mathbb{F}_{q^{d/f}}$, which becomes isomorphic via $\psi : E' \to E$ over $\mathbb{F}_{q^d}$. Working with $P', Q'$ over $E'$ rather than with $P, Q$ over $E$ can be helpful in terms of the field of definitions of their coordinates (see the paper for more details).
A word of warning: if we start with $g_{P,Q}$ normalised with respect to some uniformiser $\pi_{0_E}$ for $0_E$ (typically $\pi_{0_E} = \pm x/y$), then $\psi^*g_{P,Q}$ will be normalised for $\pi^*\pi_{0_E}$, which may not be $\pm x'/y'$. For instance in the situation of [CLN10, Theorem 1], we have $\pi^*x/y = \omega x'/y'$, which explains precisely the factor $\omega$ found from the explicit computations in the proof of that Theorem. The biextension point of view thus gives a more conceptual proof of that result (since we have seen above that Miller's algorithm is a particular way of computing the biextension arithmetic).

Let us give more details for the general case of an abelian variety. Recall that a twist $A'$ of $A$ over $k$ corresponds to an element $\zeta \in H^1(\text{Gal}(\bar{k}/k), \text{Aut}(A)(\bar{k}))$. If $k = \mathbb{F}_q$ is a finite field, this $H^1$ is isomorphic to $\text{Aut}(A)(\overline{\mathbb{F}}_q)/(\pi_q - 1)$. Let us assume that $\text{Aut}(A)(\overline{\mathbb{F}}_q) = \text{Aut}(A)(\mathbb{F}_q)$ for simplicity, so that the $H^1$ is isomorphic to $\text{Aut}(A)$. Take $\alpha \in \text{Aut}(A)$, and let $A' = A_\alpha$ be the twist corresponding to $\alpha$. Let $\phi : A \to A'$ be an isomorphism (which will be defined over the extension of $\mathbb{F}_q$ of degree $e$ the order of $\alpha$). We then have $\phi^{-1} \circ \pi_q \circ \phi = \alpha\pi_q$.

Now for the Weil pairing $e_{W,\ell}(P, Q)$, we can take any biextension element $g_{P,Q}$ above $P, Q$, and compute the Weil pairing through monodromy information. By the argument above, using the isomorphism $X_A \to X_{A'}, g_{P,Q} \mapsto g'_{P',Q'} = \phi^*g_{P,Q}$, we see that $e_{W,\ell}(P, Q) = e_{W,\ell}(P', Q')$ for $P' = \phi(P), Q' = \phi(Q)$, because the pullback of a constant function $\lambda$ by $\phi$ is still $\lambda$.

For the (reduced) Tate pairing, say over $\mathbb{F}_{q^d}$, things are more subtle: we recover it from the monodromy information $g_{P,Q}^{*1,q^d} = \lambda$ only if we take $g_{P,Q}$ rational over $\mathbb{F}_{q^d}$. But in that case, $g'_{P',Q'}$ might not be, so the two Tate pairing could differ. However, if $e|d$ (as is usually the case when using twists in pairing based cryptography), then since the isomorphism $X_A \to X_{A'}$ is defined over $\mathbb{F}_{q^c}$ then $g'_{P',Q'}$ will be rational.

Another way to see that is to use Remark 3.20: the Tate pairing is given by the monodromy $g_{P,Q}^{*1,q^d} = \lambda \pi_{q^d}(g_{P,Q})$, where this time the result does not depend on the fact that $g_{P,Q}$ is rational. Computing the monodromy on the twist, we get $g'_{P',Q'} \stackrel{*1,q^d}{=} \lambda' \pi_{q^d}(g'_{P',Q'})$, where $\lambda'$ might be different from $\lambda$ because of the relation $\phi^{-1} \circ \pi_q \circ \phi = \alpha \pi_q$, which implies that $\phi^{-1} \circ \pi_{q^d} \circ \phi = \alpha^d \pi_q$. We recover that when $e|d$, $\phi^{-1} \circ \pi_{q^d} \circ \phi = \pi_{q^d}$, hence $\lambda' = \lambda$. In the general case, if $[\phi]$ is the determinant action of $\phi$ on the differentials (i.e., its action on $\Lambda^g \Omega_{A/\mathbb{F}_q}^1$) (this depends on the choice of $[\phi]$, not only on the choice of twist $A'$), then $\lambda' = [\phi]^{q^d-1}\lambda$.

The same reasoning holds for the ate pairing, where this time we use the monodromy: $g_{P,Q}^{*1,q} = \lambda \pi_q(g_{P,Q})$, hence the same considerations as for the Tate pairing above apply with $\pi_q$ instead of $\pi_{q^d}$.

4. CUBICAL ARITHMETIC

In this section, we introduce the cubical representation of biextension elements, from which we will derive efficient biextension arithmetic on Kummer lines.

We refer to [Bre83; Mor85, Chapitre 1] for the concept of cubical torsors, and notably to [Bre83, Introduction; Mor85, Chapitre 1, § 2, 3] for illuminating discussions on the relationship between squared torsor structures, theta groups, cubical torsor structures and symmetric biextensions (notably: on an abelian variety line bundles admit squared and cubical structures, the cubical structure being induced by the squared one; and theta groups correspond to the squared structures, and symmetric biextensions to the cubical structures).
We first introduce the algebraic Riemann formulas in Section 4.1, which we use in Section 4.2 to define cubical points and an arithmetic on cubical points. We show in Section 4.3 that the cubical arithmetic is a refinement of the biextension arithmetic, and can thus be used to get a representation of biextension elements. We reframe in Section 4.4 pairings in terms of cubical points. In Section 4.5 we introduce the affine lift representation of cubical point, and compare it with the evaluation representation of Section 3.3. We show in Section 4.7 that with small tweaks, these affine lifts also give a good representation of cubical point on a Kummer variety $A/\pm 1$. In Section 4.8, for a complex abelian variety $A/\mathbb{C} = \mathbb{C}^g/\Lambda$, we make explicit the link between the cubical arithmetic and the transcendental/analytic group law on $\mathbb{C}^g$. We then specialize our formulas to the case of elliptic curves in Section 4.9.

**4.1. The algebraic Riemann formulas.** Let $D$ be an ample divisor on an abelian variety. We will assume that $D$ is symmetric up to linear equivalence, ie $[-1]^*D \sim D$. Upon changing $D$ in its algebraic equivalence class, which does not changes the associated polarisation, we can always assume this is the case (possibly over a field extension). Changing $D$ in its linear equivalence class (possibly over a field extension again), we could even assume that $D$ is symmetric.

**Proposition 4.1.** Let $P_1, P_2, P_3, P_4 \in A$, $2R = P_1 + P_2 + P_3 + P_4$, and $Q_1 = R - P_1$, $Q_2 = R - P_2$, $Q_3 = R - P_3$, $Q_4 = R - P_4$ (we remark that $2R = Q_1 + Q_2 + Q_3 + Q_4$ and $P_i = R - Q_i$ so the situation is symmetric in the $P_i, Q_i$). There is a canonical function $\gamma$ whose divisor is $D_{P_1} + D_{P_2} + D_{P_3} + D_{P_4} - D_{Q_1} - D_{Q_2} - D_{Q_3} - D_{Q_4}$.

It is convenient to reframe this in terms of line bundles: let $\mathcal{L} = O(D)$ be the associated symmetric line bundle. Denote by $\mathcal{L}_P$ the translate $t_P^*\mathcal{L}$. Then there is a canonical isomorphism

$$ (16) \qquad \mathcal{L}_{P_1} \otimes \mathcal{L}_{P_2} \otimes \mathcal{L}_{P_3} \otimes \mathcal{L}_{P_4} \simeq \mathcal{L}_{Q_1} \otimes \mathcal{L}_{Q_2} \otimes \mathcal{L}_{Q_3} \otimes \mathcal{L}_{Q_4} $$

We call this isomorphism an algebraic Riemann relation, and use the notation $[P_1, P_2, P_3, P_4; Q_1, Q_2, Q_3, Q_4]$ to denote that the points $P_i, Q_i$ are in Riemann form.

*Proof.* We have $D_{Q_3} + D_{Q_4} = 2D_R - D_{P_3} - D_{P_4} = D_{P_1} + D_{P_2}$. Hence, there exists some (non canonical) function $\alpha$ with divisor $D_{P_1} + D_{P_2} - D_{Q_3} - D_{Q_4}$. Now $[-1]^*\alpha$ has for divisor $([ -1 ]^*D)_{-P_1} + ([ -1 ]^*D)_{-P_2} - ([ -1 ]^*D)_{-Q_3} - ([ -1 ]^*D)_{-Q_4}$, so $t_R^*[-1]^*\alpha = \alpha(R - (\cdot))$ has for divisor $([ -1 ]^*D)_{R - P_1} + ([ -1 ]^*D)_{R - P_2} - ([ -1 ]^*D)_{R - Q_3} - ([ -1 ]^*D)_{R - Q_4} = ([ -1 ]^*D)_{Q_1} + ([ -1 ]^*D)_{Q_2} - ([ -1 ]^*D)_{P_3} - ([ -1 ]^*D)_{P_4}$.

Since $D$ is linearly equivalent to $[-1]^*D$, there exists some function $\beta$ with divisor $[-1]^*D - D$. It follows that $\alpha(R - (\cdot)) \frac{\beta(\cdot + Q_1)\beta(\cdot + Q_2)}{\beta(\cdot + P_3)\beta(\cdot + Q_4)}$ has for divisor $D_{Q_1} + D_{Q_2} - D_{P_3} - D_{P_4}$. Hence the function

$$ \gamma = \frac{\alpha(\cdot)}{\alpha(R - (\cdot))} \frac{\beta(\cdot + Q_1)\beta(\cdot + Q_2)}{\beta(\cdot + P_3)\beta(\cdot + Q_4)} $$

has for divisor $D_{P_1} + D_{P_2} - D_{Q_3} - D_{Q_4} - D_{Q_1} - D_{Q_2} + D_{P_3} + D_{P_4}$ as wanted, and it does not depend on our choice of $\alpha, \beta$.

Using the language of line bundles, the proof simplifies as follows: fix an arbitrary isomorphism $\alpha : \mathcal{L}_{P_1} \otimes \mathcal{L}_{P_2} \to \mathcal{L}_{Q_3} \otimes \mathcal{L}_{Q_4}$ and use $t_R^*[-1]^*\alpha$ along with any isomorphism $\delta : [-1]^*\mathcal{L} \simeq \mathcal{L}$ (in practice it will be convenient to use the canonical one rigidified at 0) to obtain an isomorphism $\alpha_2 : \mathcal{L}_{Q_1} \otimes \mathcal{L}_{Q_2} \to \mathcal{L}_{P_3} \otimes \mathcal{L}_{P_4}$. We then have an isomorphism $\gamma = \alpha \otimes \alpha_2^{-1} : \mathcal{L}_{P_1} \otimes \mathcal{L}_{P_2} \otimes \mathcal{L}_{P_3} \otimes \mathcal{L}_{P_4} \simeq \mathcal{L}_{Q_1} \otimes \mathcal{L}_{Q_2} \otimes \mathcal{L}_{Q_3} \otimes \mathcal{L}_{Q_4}$ which does not depend on the choice of $\alpha$. $\square$

**Remark 4.2.** We remark that if $D$ is symmetric, we can take $\beta = 1$ and the function $\gamma$ simplifies to $\gamma = \frac{\alpha(\cdot)}{\alpha(R - (\cdot))}$.
For instance, this is the case if $A = E$ is an elliptic curve and $D = (0_E)$; we recall that $\alpha$ is any function with divisor $D_{P_1} + D_{P_2} - D_{Q_3} - D_{Q_4}$. An explicit construction of $\alpha$ is as follows: recall that $Q_3 + Q_4 = R - P_3 + R - P_4 = P_1 + P_2$. Let $g_{P_1,P_2}$ be any function with divisor $D_{P_1+P_2} - D_{P_1} - D_{P_2}$ and $g_{Q_3,Q_4}$ be any function with divisor $D_{Q_3+Q_4} - D_{Q_3} - D_{Q_4}$, then $\alpha = g_{Q_3,Q_4}/g_{P_1,P_2}$ has the correct divisor, and we obtain

$$ \gamma(X) = \frac{g_{Q_3,Q_4}(X)g_{P_1,P_2}(R-X)}{g_{P_1,P_2}(X)g_{Q_3,Q_4}(R-X)}. $$

We also remark that $\gamma$ is constructed from $\alpha$, whose existence comes from the theorem of the square. On an abelian variety a line bundle has a canonical squared structure which induces the canonical cubical structure.

**Example 4.3.** We have the following important squared and cubical relations (compare with [Mor85, § I.2.3] and [Mor85, I.(2.4.1)] respectively) as special cases of Proposition 4.1 and Remark 4.2:

* $[P+Q, P-Q, 0, 0; -Q, Q, P, P]$. If $D$ is symmetric, the function $\gamma$ associated to $[P+Q, P-Q, 0, 0; -Q, Q, P, P]$ is $\gamma = \frac{g_{Q,-Q}(P-\cdot)}{g_{Q,-Q}(\cdot)}$, with $g_{Q,-Q}$ a function with divisor $D_Q + D_{-Q}$.

* $[P+Q+R, P, Q, R; 0, Q+R, P+R, P+Q]$. If $D$ is symmetric, the function $\gamma$ associated to $[P+Q+R, P, Q, R; 0, Q+R, P+R, P+Q]$ is $\gamma = \frac{g_{Q,R}(P+Q+R-\cdot)}{g_{Q,R}(\cdot)}$ with $g_{Q,R}$ a function with divisor $D_{Q+R} - D_Q - D_R$.

A trick to find $\gamma$ in practice is to remark that $\gamma$ has for divisor $D_{P+Q} + D_{P-Q} - D_{-Q} - D_Q - 2D_P$ and $D_{P+Q+R} + D_P + D_Q + D_R - D_{Q+R} - D_{P+R} - D_{P+Q}$ respectively, and satisfy the equation $\gamma(\cdot)\gamma(T-\cdot) = 1$ where $T = P$ and $T = P+Q+R$ respectively. (More generally, if $[P_1, P_2, P_3, P_4; Q_1, Q_2, Q_3, Q_4]$ are in Riemann positions, $\gamma$ has for divisor $D_{P_1} + D_{P_2} + D_{P_3} + D_{P_4} - D_{Q_1} - D_{Q_2} - D_{Q_3} - D_{Q_4}$ and $2T = P_1 + P_2 + P_3 + P_4$.) In particular, if $T = 2T'$, $\gamma(T')^2 = 1$, so $\gamma$ is determined up to a sign from its divisor and this equation.

**4.2. Cubical structure and cubical arithmetic.** We can use Proposition 4.1 to define a "cubical arithmetic".

**4.2.1. Normalised symmetric isomorphism.** Let $\mathcal{L}$ be a symmetric line bundle on $A$, and $\alpha : \mathcal{L} \simeq [-1]^*\mathcal{L}$ an isomorphism.

Then if $P \in A$, $\alpha$ induces $\alpha(P) : \mathcal{L}(P) \simeq ([-1]^*\mathcal{L})(P) = \mathcal{L}(-P)$.

Following [Mum66, § 2], we call $\alpha$ normalised if $\alpha(0_A)$ is the identity map; such an isomorphism always exist.

**4.2.2. Rigidifications.** When $\mathcal{L}$ is a line bundle on an abelian variety $A$, we recall that a rigidification of $\mathcal{L}$ at a point $P \in A$ is the choice of an isomorphism $O_A(P) \to \mathcal{L}(P) := \mathcal{L} \otimes O_A(P)$ (we will take our rigidifications to be rational). The rigidifications at $P$ form a torsor under $\mathbb{G}_m$.

We remark that a line bundle is locally trivial for the Zariski topology, so we can always find a local trivialisation around $P$ given by an isomorphism $O_{A,P} \to \mathcal{L} \otimes O_{A,P}$. A trivialisation $\phi_P : O_{A,P} \simeq \mathcal{L} \otimes O_{A,P}$ induces an isomorphism on the residual fibers: $\phi_P : k(P) \simeq \mathcal{L}(P) := \mathcal{L} \otimes k(P)$, so a rigidification at $P$.

Conversely, a rigidification, i.e. an isomorphism on the fibers always lift (non uniquely) to a local trivialisation. Looking at the image of $1 \in O$ under a trivialisation, we see that a choice of trivialisation is the same as a choice of local section $s$ of $\mathcal{L}$ at $P$ which generates
L locally at P, or equivalently $s(P) \neq 0$ (the value of $s$ at $P$ is not well defined, but the fact that it is zero or not is). Reformulated in terms of a divisor $D$ associated to $L$, a local section $s$ is a function such that $\text{div}(s) + D$ has no poles at $P$, and $s$ generates $L$ locally at $P$ if for all other local sections $t$, the function $t/s$ does not have a pole at $P$. Trivialisations are more conveniently expressed in terms of line bundles, which is why we have started to switch to this language in Section 4.1. Two local trivialisations, induced by local sections $s_1, s_2$, give the same rigidification at $P$ iff $(s_1/s_2)(P) = 1$.

Furthermore if $L \simeq M$, then since $A/k$ is proper and integral, $\text{Hom}(L, M) \simeq \Gamma(A) \simeq k$. So a rigidification of $L, M$ at $P$ is enough to fix uniquely a global isomorphism $L \to M$.

**4.2.3. Cubical torsor structure.** Let $M \in \text{Pic}^0(A)$, $m: A \times A \to A$ be given by the addition map, and $\pi_1, \pi_2$ the two projections. Consider the line bundle $\Lambda M = m^*M \otimes \pi_1^*M^{-1} \otimes \pi_2^*M^{-1}$. Since $M$ is algebraically equivalent to 0, it is translation invariant, so $\Lambda M$ is fiberwise trivial, hence is trivial by the seesaw theorem; it is completely rigidified by a rigidification of $M$ at $0_A$. In particular, once a rigidification at $0_A$ of $M$ is fixed, we have canonical isomorphisms $M(Q_1 + Q_2) \to M(Q_1) \otimes M(Q_2)$, satisfying various natural compatibility relations on $A \times A \times A$. This is the squared structure associated to a line bundle algebraically equivalent to 0.

Now if $L$ is a line bundle, then $M_P := t_P^*L \otimes L^{-1}$ is algebraically equivalent to 0. Fixing a rigidification of $L$ at $0_A$, we obtain canonical isomorphisms $L(P+Q_1+Q_2) \otimes L(Q_1) \otimes L(Q_2) \simeq L(P+Q_1) \otimes L(P+Q_2) \otimes L(Q_1+Q_2)$, which depends on a choice of rigidification of $M_P$ at $0_A$. These isomorphisms are subsumed as follows: let $m_{123}: A \times A \times A \to A$, $(P_1, P_2, P_3) \to P_1+P_2+P_3$, $m_{ij}: A \times A \times A \to A$, $(P_1, P_2, P_3) \to P_i+P_j$ and $m_i = \pi_i$ the projection map. Consider the line bundle $m_{123}^*L \otimes m_{12}^*L^{-1} \otimes m_{23}^*L^{-1} \otimes m_{13}^*L^{-1} \otimes m_1^*L \otimes m_2^*L \otimes m_3^*L$. Then the theorem of the cube implies that this torsor is trivial, and globally rigidified by a rigidification of $L$ at $0_A$. This is the cubical structure associated to a line bundle $L$; by the discussion above this cubical structure can be recovered from the squared structures on the $M_P$.

**4.2.4. Cubical arithmetic.** On an abelian variety $A$, fixing a rigidification of $L$ at $P$ is the same as fixing a rigidification of $L_P := t_P^*L$ at $0_A$: a local isomorphism $\phi: O_A(0_A) \to L_P(0_A)$ at $0_A$ induces by pullback a local isomorphism $t_P^*\phi: O_A(P) \to L(P)$ at $P$.

Given $P \in A$, we will denote by $\tilde{P}$ the choice of a rigidification $\phi_{\tilde{P}}$ of $L_P$ (implicitly at $0_A$). If $\lambda \in \mathbb{G}_m$, we will denote by $\lambda\tilde{P}$ the rigidification $\lambda\phi_{\tilde{P}}$. We will call $\tilde{P}$ a cubical point; the reason for the terminology and the notation will become clear in Section 4.5 where we introduce a convenient way to represent $\phi_{\tilde{P}}$: a cubical point $\tilde{P}$ is a “point” lying above the projective point $P$, with a cubical arithmetic induced from Section 4.2.3.

The cubical arithmetic may be defined as follows: if we have fixed a rigidification of $L$ at $0_A$ and rigidifications of $L$ at $P_1, P_2, P_3, P_1+P_2, P_1+P_3, P_2+P_3$, then by the cubical structure, using the canonical isomorphism $L(P_1+P_2+P_3) \otimes L(P_1) \otimes L(P_2) \otimes L(P_3) \simeq L(P_1+P_2) \otimes L(P_1+P_3) \otimes L(P_2+P_3)$, we have a canonical rigidification of $L$ at $P_1+P_2+P_3$.

More generally, we can use the algebraic Riemann relations. Let $[P_1, P_2, P_3, P_4; Q_1, Q_2, Q_3, Q_4]$ be points in Riemann position. By Proposition 4.1, given a rigidification $\tilde{P}_i, \tilde{Q}_i$ on seven out of our eight points $P_i, Q_i$, there is a *canonical* rigidification associated to the last one. We call the corresponding rigidification the one induced by the cubical arithmetic. We then say that the cubical points $[\tilde{P}_1, \tilde{P}_2, \tilde{P}_3, \tilde{P}_4; \tilde{Q}_1, \tilde{Q}_2, \tilde{Q}_3, \tilde{Q}_4]$ are in Riemann position.
**Example 4.4.** By Example 4.3, we have the following special cases of cubical arithmetic. We fix once and for all a choice for $\tilde{0}_A$.

* Given $\tilde{P}, \tilde{Q}, P-Q$, we have a canonical rigidification $P+Q$, which we call a cubical differential addition. We denote $P+Q = \text{DiffAdd}(\tilde{P}, \tilde{Q}, P-Q)$. As a special case where $\tilde{P} = \tilde{Q}$ and $P-Q = \tilde{0}_A$, we have a cubical doubling $2\tilde{P} = \text{Double}(\tilde{P})$.

* Given $\tilde{P}, \tilde{Q}, \tilde{R}, P+Q, P+R, Q+R$, we have a canonical rigidification $P+\tilde{Q}+R$, which we call a cubical three way add. We denote $P+\tilde{Q}+R = \text{ThreeWayAdd}(\tilde{P}, \tilde{Q}, \tilde{R}, P+\tilde{Q}, P+R, \tilde{Q}+R)$.

* More generally, given points $\tilde{P}_i$ and their two by two sums $P_i + P_j$, we can compute a multi way addition $P_1 + \cdots + P_m$ by iterating multiple three way additions.

In particular, given $\tilde{P}$ we can use a ladder cubical differential additions and doublings to compute a cubical scalar multiplication $\ell \tilde{P}$. Likewise, given $P+Q, \tilde{P}, \tilde{Q}$, we can compute $\ell \tilde{P}+Q$ though a ladder. We will denote $\ell \tilde{P}+Q = \text{ScalarMult}(\ell, P+Q, \tilde{P}, \tilde{Q})$ and $\ell \tilde{P} = \text{ScalarMult}(\ell, \tilde{P})$.

We can also define the opposite of a point as follows. Since $\mathcal{L}$ is symmetric, we take the normalised isomorphism $\alpha : [-1]^*\mathcal{L} \simeq \mathcal{L}$. If $\tilde{P}$ is a rigidification of $\mathcal{L}$ at $P$, $[-1]^*\tilde{P}$ is a rigidification of $[-1]^*\mathcal{L}$ at $-P$, and we can use the isomorphism above to obtain a rigidification of $\mathcal{L}$ at $-P$, which we denote by $-\tilde{P}$. Since we use the normalised symmetric isomorphism, we have $-\tilde{0}_A = \tilde{0}_A$.

The cubical arithmetic is homogeneous with respect to the action by $\mathbb{G}_m$. (We recall that if $\tilde{P}$ is a cubical point corresponding to an isomorphism $O_A(P) \to \mathcal{L}(P)$, $\lambda \tilde{P}$ is the cubical point corresponding to this isomorphism multiplied by $\lambda$.) More precisely, we have:

**Lemma 4.5.**

* If $[\tilde{P}_1, \tilde{P}_2, \tilde{P}_3, \tilde{P}_4; \tilde{Q}_1, \tilde{Q}_2, \tilde{Q}_3, \tilde{Q}_4]$ are in Riemann position, then so are $[\lambda_{P_1} \tilde{P}_1, \lambda_{P_2} \tilde{P}_2, \lambda_{P_3} \tilde{P}_3, \lambda_{P_4} \tilde{P}_4; \lambda_{Q_1} \tilde{Q}_1, \lambda_{Q_2} \tilde{Q}_2, \lambda_{Q_3} \tilde{Q}_3, \lambda_{Q_4} \tilde{Q}_4]$ whenever $\lambda_{P_1} \lambda_{P_2} \lambda_{P_3} \lambda_{P_4} = \lambda_{Q_1} \lambda_{Q_2} \lambda_{Q_3} \lambda_{Q_4}$;

$$-(\lambda \tilde{P}) = \lambda(-\tilde{P})$$

$$\text{DiffAdd}(\lambda_P \tilde{P}, \lambda_Q \tilde{Q}, \lambda_{PQ} \tilde{P} - \tilde{Q}, \lambda_0 \tilde{\Omega}) = \frac{\lambda_P^2 \lambda_Q^2}{\lambda_{PQ} \lambda_0^2} \text{DiffAdd}(\tilde{P}, \tilde{Q}, \tilde{P} - \tilde{Q}, \tilde{\Omega});$$

$$\text{ThreeWayAdd}(\lambda_{P_1} \tilde{P}_1, \lambda_{P_2} \tilde{P}_2, \lambda_{P_3} \tilde{P}_3, \lambda_{P_2+P_3} P_2 + \tilde{P}_3, \lambda_{P_1+P_3} P_1 + \tilde{P}_3, \lambda_{P_1+P_2} P_1 + \tilde{P}_2, \lambda_0 \tilde{\Omega}) = \frac{\lambda_{P_1+P_2} \lambda_{P_2+P_3} \lambda_{P_1+P_3} \lambda_0}{\lambda_{P_1} \lambda_{P_2} \lambda_{P_3}} \text{ThreeWayAdd}(\tilde{P}_1, \tilde{P}_2, \tilde{P}_3, P_2 + \tilde{P}_3, P_1 + \tilde{P}_3, P_1 + \tilde{P}_2, \tilde{\Omega})$$

$$\text{ScalarMult}(\ell, \lambda_{PQ} \tilde{P} + \tilde{Q}, \lambda_P \tilde{P}, \lambda_Q \tilde{Q}, \lambda_0 \tilde{\Omega}) = \lambda_{PQ}^{\ell} \lambda_P^{\ell(\ell-1)} \lambda_Q^{-\ell(\ell-1)} \lambda_0^{-\ell(\ell-1)} \lambda_P^{\ell_2} \text{ScalarMult}(\ell, \tilde{P} + \tilde{Q}, \tilde{P}, \tilde{Q}, \tilde{\Omega})$$

We warn that the cubical arithmetic defined in Example 4.4 does not form a group structure (unlike biextensions which do induce compatible groups structures on subsets). The cubical arithmetic shares many analogy with the arithmetic of a Kummer variety. Furthermore, using [Mor85, § I.5], all expected natural relations do hold in the cubical arithmetic. We note also that if $P$ is a point of $\ell$-torsion and we fix a rigidification $\tilde{P}$, then $\ell \tilde{P}$ is a rigidification of $\mathcal{L}$ at $0_A$ so differ from our global choice of $\tilde{0}_{A_k}$ by some constant $\lambda$: $\ell \tilde{P} = \lambda \tilde{0}_{A_k}$. In general, we will have $\lambda \neq 1$ (i.e., $\tilde{P}$ will not be of $\ell$-torsion), in fact constants like $\lambda$ will provide us exactly the monodromy informations which gives the Weil and Tate pairings.

### 4.2.5. Cubical nets.
Assume that we are given $r$ points $P_i \in A$, and that we have fixed cubical points $\tilde{P}_i$ and $P_i + P_j$ for all $i \neq j$. Then for each $n = (n_1, \dots, n_r) \in \mathbb{Z}^r$, the cubical arithmetic determines a cubical point $\sum n_i \tilde{P}_i := \sum n_i P_i$. (For the link with elliptic nets, we refer to Section 4.9.5).

The compatibility relations for the cubical torsor structure show that we can use whichever Riemann relations to arrive at the end result, they all give the same cubical points. For instance,
we can compute $2P_1 + 2P_2$ as Double($P_1 + P_2$), or by computing successively via doublings and differential additions $2\overline{P}_1$, $2P_1 + P_2$, $2P_1 + 2P_2$, or doing it the other way around: $2\overline{P}_2$, $2P_2 + P_1$, $2P_1 + 2P_2$. The end result is the same.

**Remark 4.6.** One should be careful that if $P_1$ is a point of $\ell_1$ torsion, $\sum \widetilde{n_i}P_i$ and $\ell_1P_1 + \sum \widetilde{n_i}P_i$ will not give the same cubical point in general; they differ by some projective factor $\lambda_{P_1}$. This is the whole point of the cubical arithmetic; this monodromy will give pairings.

We can extend Lemma 4.5 by recurrence on the rank $r$ (compare with [Stao8, Proposition 5.1.2, Theorem 6.2.3, Theorem 10.1.1]):

**Lemma 4.7.** If we change $\widetilde{P}_i$ into $\lambda_i\widetilde{P}_i$, and $P_i + \widetilde{P}_j$ into $\lambda_{ij}P_i + \widetilde{P}_j$, then $\sum \widetilde{n_i}P_i$ is changed into

$$ \prod_i \lambda_i^{n_i^2} \prod_{i<j} \left( \frac{\lambda_{ij}}{\lambda_i \lambda_j} \right)^{n_i n_j} \sum \widetilde{n_i} P_i. $$

A convenient way to remember Lemma 4.7, which I learnt from [Stao8, § 10.3], is to write $\lambda'_{ii} = \lambda_i$, $\lambda_{ij} = (\lambda'_{ij})^2\lambda_i\lambda_j$ (we will see that the choice of square root for $\lambda'_{ij}$ does not matter). Then if we write a formal square $(\sum n_i x_i)^2 = \sum_i n_i^2 x_i^2 + \sum_{i<j} 2n_i n_j x_i x_j = \sum_{i \le j} c_{ij} x_i x_j$, we see that $\sum \widetilde{n_i}P_i$ is changed into $\prod_{i \le j} \lambda'_{ij} c_{ij} \sum \widetilde{n_i}P_i$.

**Lemma 4.8 (Periodicity).** Let $\Gamma \subset \mathbb{Z}^r$ be the lattice of relations on the $P_i$: for all $\gamma = (\gamma_1, \dots, \gamma_r) \in \Gamma$, $\sum \gamma_i P_i = 0$.

Then for all $n \in \mathbb{Z}^r$, $\gamma \in \Gamma$, the two cubical points $\sum n_i \widetilde{P}_i$ and $\sum (n_i + \gamma_i) \widetilde{P}_i$ lie over the same point $\sum n_i P_i$, so differ by a projective factor $\lambda(\gamma, n)$: $\sum (n_i + \gamma_i) \widetilde{P}_i = \lambda(\gamma, n) \sum \widetilde{n_i} P_i$.

Then $\lambda$ is quadratic, and affine linear in $n$: for $\gamma_1, \gamma_2, \gamma_3 \in \Gamma$, $n_1, n_2, n_3 \in \mathbb{Z}^r$,

$$ \lambda(\gamma_1 + \gamma_2 + \gamma_3, n_1 + n_2 + n_3)\lambda(\gamma_1, n_1)\lambda(\gamma_2, n_2)\lambda(\gamma_3, n_3) = \lambda(\gamma_1 + \gamma_2, n_1 + n_2)\lambda(\gamma_2 + \gamma_3, n_2 + n_3)\lambda(\gamma_1 + \gamma_3, n_1 + n_2) \\ \lambda(\gamma, n_1 + n_2 + n_3)\lambda(\gamma, n_3) = \lambda(\gamma, n_1 + n_3)\lambda(\gamma, n_2 + n_3). $$

*Proof.* Using Lemma 4.7, the proof is the same as in [Stao8, Theorem 10.2.3] (except that our $\lambda$ is well defined everywhere, so this simplifies a bit the proof). $\square$

**Example 4.9.** If $P$ is a point of $\ell$-torsion and we fix a cubical point $\widetilde{P}$, then writing $\ell\widetilde{P} = \lambda_0\tilde{0}$, $(\ell + 1)\widetilde{P} = \lambda_1\widetilde{P}$, with $\lambda_1 = \lambda_0\lambda'_1$, we have $(u\ell + v)\widetilde{P} = \lambda_0^{u2}\lambda_1'^{uv}v\widetilde{P}$, and writing $2\ell\widetilde{P} = \ell\widetilde{P} + \ell\widetilde{P}$, we obtain $\lambda_0^2 = \lambda_1'^{\ell}$, as in [Stao8, Theorem 10.2.2]. So if we let $\alpha, \beta \in \bar{k}$ such that<fnref n="1" /> $\beta^\ell = \lambda_0, \beta^2 = \lambda_1' \alpha^\ell = \beta$, we have $(u\ell + v)\widetilde{P} = \beta^{\ell(u2+2uv)}v\widetilde{P} = \alpha^{(u\ell+v)^2-v^2}v\widetilde{P}$. (There is a small typo in [Stao8, Theorem 10.2.2], the $\alpha$ defined there is our $\beta$, but the formula is only correct using the $\alpha$ we define here.)

We will see in Section 4.4 that $\lambda'_1$ is the self Tate pairing $e_{T,\ell}(P, P)$. Furthermore, if $\ell = 2\ell' + 1$ is odd, then $(\ell' + 1)\widetilde{P} = \beta \cdot -\ell'\widetilde{P}$, and if $\ell = 2\ell' + 2$ is even, $(\ell' + 2)\widetilde{P} = \beta^2 \cdot -\ell'\widetilde{P}$.

**Example 4.10.** If $\ell_1 P + \ell_2 Q = 0$, and we fix $\widetilde{P}, \widetilde{Q}, P + Q$, we have $(u\ell_1 + v_1)P + (u\ell_2 + v_2)Q = \lambda'_P^{uv_1}\lambda'_Q^{uv_2}\lambda_{PQ}^{u2}v_1P + v_2Q$ where $2P + (\ell_1\widetilde{P} + \ell_2Q) = \lambda'_P 2\widetilde{P}$, $2Q + (\ell_1\widetilde{P} + \ell_2Q) = \lambda'_Q 2\widetilde{Q}$, $P + Q + (\ell_1\widetilde{P} + \ell_2Q) = \lambda'_P \lambda'_Q \lambda_{PQ}P + Q$. Compare with [Stao8, Lemma 10.2.5].

Using that $\lambda$ is defined everywhere, we can also recover these projective factors as follows: $\ell_1 P + \ell_2 Q = \lambda_{PQ}\tilde{0}$, $P + \ell_1\widetilde{P} + \ell_2Q = \lambda'_P \lambda_{PQ}\widetilde{P}$, $Q + \ell_1\widetilde{P} + \ell_2Q = \lambda'_Q \lambda_{PQ}\tilde{Q}$.

<footnote n="1">¹This is always possible if $\ell$ is odd; if $\ell$ is even we will see in Section 6.2.2 that this is possible if and only if $e_{D,*}(\ell/2P) = 1$.</footnote>
**4.3. The cubical representation of the biextension.** We can now define the cubical representation of a biextension element $g_{P,Q} \in X_D$. Recall that the function $g_{P,Q}$ has for divisor $D_{P+Q} + D - D_P - D_Q$; in terms of line bundles it corresponds to an isomorphism $\mathcal{L}_P \otimes \mathcal{L}_Q \simeq \mathcal{L}_{P+Q} \otimes \mathcal{L}$ where $\mathcal{L} = O(D)$ is the line bundle associated to $D$.

We can proceed as in Section 4.2.7 for the cycle $Z = (P+Q) + (0) - (P) - (Q)$. Namely assume that we are given local rigidifications at $0, \tilde{0}, \tilde{P}, \tilde{Q}, \tilde{P}+\tilde{Q}$, of $\mathcal{L}, \mathcal{L}_P, \mathcal{L}_Q, \mathcal{L}_{PQ}$ respectively. These give a local isomorphism $\mathcal{L}_P \otimes \mathcal{L}_Q \to \mathcal{L}_{P+Q} \otimes \mathcal{L}$ at $0$. Since these line bundles are globally isomorphic, this local isomorphism lift to a unique global isomorphism, hence defines a biextension element which we denote by $(P, Q, g_{P,Q}) = [\tilde{P}, \tilde{Q}; \tilde{0}, \tilde{P}+\tilde{Q}]$. (We will often assume $\tilde{0}$ has been fixed once and for all and drop it from our notations). We call this the cubical representation of the biextension. It is convenient to also use a two dimensional notation:

$$(P, Q, g_{P,Q}) = \begin{pmatrix} \tilde{0} & \tilde{P} \\ \tilde{Q} & P+\tilde{Q} \end{pmatrix}.$$

Recall that $\tilde{P}$ is a notation for a rigidification $\phi_{\tilde{P}} : O_A(0) \to \mathcal{L}_P(0)$ at $0$, so by abuse of notations we denote by $P+\tilde{Q} \otimes \tilde{0} \otimes \tilde{P}^{-1} \otimes \tilde{Q}^{-1}$ (or even $\frac{P+\tilde{Q}\tilde{0}}{\tilde{P}\tilde{Q}}$) the corresponding tensor product of rigidifications $O_A(0) \to \mathcal{L}_{P+Q}(0) \otimes \mathcal{L}(0) \otimes \mathcal{L}_P^{-1}(0) \otimes \mathcal{L}_Q^{-1}(0)$. The rigidification $\frac{P+\tilde{Q}\tilde{0}}{\tilde{P}\tilde{Q}}$ lift to a global trivialisation, which is associated precisely to the biextension function $g_{P,Q}$ given by the cubical representation.

**Remark 4.14.** This representation is quite similar to the evaluation representation; instead of representing $g_{P,Q}$ through its extended value at $0$, we use a rigidification of $\mathcal{L}_{P+Q} \otimes \mathcal{L} \otimes \mathcal{L}_P^{-1} \otimes \mathcal{L}_Q^{-1}$ at $0$. We refer to Section 4.5 for the relationship between the two representations. The advantage of the latter representation is that it can be further refined though local rigidifications of $\mathcal{L}_{P+Q}, \mathcal{L}_P, \mathcal{L}_Q, \dots$ at $0$ (which do not come from global functions evaluated at $0$ since these line bundles are not trivial individually).

In the evaluation representation we could change our evaluation point from $0$ to $R_0$; likewise here we could use instead a representation of the form

$$(P, Q, g_{P,Q}) = \begin{pmatrix} \tilde{R}_0 & P+\tilde{R}_0 \\ Q+R_0 & P+\tilde{Q}+R_0 \end{pmatrix}.$$

We could even use the cubical three way add introduced below to change the base point $R_0$ of our representation on the fly; but on the following we will stick to using $R_0 = 0$ for simplicity.

We remark that this representation is redundant: the possible choices of $g_{P,Q}$ form a $\mathbb{G}_m$-torsor, while the choice on the right hand choice consist of four $\mathbb{G}_m$-torsors. From the definition, we have:

**Lemma 4.15.** Given $\lambda_0, \lambda_P, \lambda_Q, \lambda_{PQ} \in \mathbb{G}_m$, we have

$$[\lambda_P \tilde{P}, \lambda_Q \tilde{Q}; \lambda_0 \tilde{0}, \lambda_{PQ} \tilde{P}+\tilde{Q}] = \frac{\lambda_{PQ} \lambda_0}{\lambda_P \lambda_Q} [\tilde{P}, \tilde{Q}; \tilde{0}, \tilde{P}+\tilde{Q}],$$

so they define the same biextension element if and only if $\lambda_{PQ}\lambda_0 = \lambda_P\lambda_Q$.

We will see that although it is redundant, the cubical representation give a fast biextension arithmetic. An analogy is using the redundant modified Jacobian coordinates $(X, Y, Z, T)$ to compute the scalar multiplication of an elliptic curve.
Now we explain how to recover the biextension arithmetic in term of our cubical representation and the cubical arithmetic. There are actually several possibilities (the cubical arithmetic is a refinement of the biextension arithmetic), and we will focus on two specific formulas.

**Theorem 4.16.** Fix $\tilde{0}$, and let $\tilde{P}_1, \tilde{P}_2, P_1 + \tilde{Q}, P_2 + \tilde{Q}$ be cubical points, and let $g_{P_1,Q} = [\tilde{P}_1, \tilde{Q}; \tilde{0}, P_1 + \tilde{Q}]$, $g_{P_2,Q} = [\tilde{P}_1, \tilde{Q}; \tilde{0}, P_2 + \tilde{Q}]$ the associated biextension elements. (We can always use Lemma 4.15 to ensure that our representation use the same $\tilde{Q}$).

Take $P_1 + \tilde{P}_2$ an arbitrary cubical point above $P_1 + \tilde{P}_2$ and let

$$P_1 + \tilde{P}_2 + \tilde{Q} = \text{ThreeWayAdd}(\tilde{P}_1, \tilde{P}_2, \tilde{Q}, P_2 + \tilde{Q}, P_1 + \tilde{Q}, P_1 + \tilde{P}_2).$$

Then $g_{P_1,Q} *_1 g_{P_2,Q} = [P_1 + \tilde{P}_2, \tilde{Q}; \tilde{0}, P_1 + \tilde{P}_2 + \tilde{Q}]$. We call this a (cubical) biextension standard addition.

Alternatively, assume that $[P_1 - \tilde{P}_2, \tilde{Q}; \tilde{0}, P_1 - \tilde{P}_2 + \tilde{Q}]$ is a cubical representation of $g_{P_1-P_2,Q} = g_{P_1,Q} *_1 g_{P_2,Q}^{*1,-1}$. Let $P_1 + \tilde{P}_2 = \text{DiffAdd}(\tilde{P}_1, \tilde{P}_2, P_1 - \tilde{P}_2)$ and $P_1 + \tilde{P}_2 + \tilde{Q} = \text{DiffAdd}(P_1 + \tilde{Q}, \tilde{P}_2, P_1 - \tilde{P}_2 + \tilde{Q})$. Then $g_{P_1,Q} *_1 g_{P_2,Q} = [P_1 + \tilde{P}_2, \tilde{Q}; \tilde{0}, P_1 + \tilde{P}_2 + \tilde{Q}]$. We call this a (cubical) biextension differential addition.

As a particular case, when $P_1 = P_2 = P$, and we have $g_{P,Q} = [\tilde{P}, \tilde{Q}; \tilde{0}, P + \tilde{Q}]$, we can take $g_{0,Q} = 1 = [\tilde{0}, \tilde{Q}; \tilde{0}, \tilde{0}]$, so if we let $2\tilde{P} = \text{Double}(\tilde{P})$ and $2\tilde{P} + \tilde{Q} = \text{DiffAdd}(P + \tilde{Q}, \tilde{P}, \tilde{Q})$, we have: $g_{P,Q} *_1 g_{P,Q} = [2\tilde{P}, \tilde{Q}; \tilde{0}, 2\tilde{P} + \tilde{Q}]$. We call this a (cubical) biextension differential doubling.

*Proof.* This is a translation of the fact, explained in [Bre83; Mor85, Chapitre 1], that the cubical structure induce a symmetric biextension, and the various natural compatibilities of the cubical arithmetic, to which we refer to [Mor85, § I.5]. We will also give an analytical argument in Section 4.8.

For the reader who does not like abstract proofs, we will prove the first statement using the explicit formulas of Proposition 4.1 and leave the second as an exercise.

By definition of the cubical representation $[\tilde{P}_i, \tilde{Q}; \tilde{0}, P_i + \tilde{Q}]$, the rigidification $P_i + \tilde{Q} \otimes \tilde{0} \otimes \tilde{P}_i^{-1} \otimes \tilde{Q}^{-1}$ globalises to a global trivialisation, which from the divisor point of view corresponds to a function $g_{P_i,Q}$ with divisor $D_{P_i+\tilde{Q}} - D_{P_i} - D_Q$.

We will assume $D$ symmetric by simplicity. By Example 4.3, the point $P_1 + \tilde{P}_2 + \tilde{Q}$ computed through the cubical arithmetic is such that $P_1 + \tilde{P}_2 + \tilde{Q} \otimes \tilde{P}_1 \otimes \tilde{P}_2 \otimes \tilde{Q} \otimes \tilde{0}^{-1} \otimes \tilde{P}_2 + \tilde{Q}^{-1} \otimes P_1 + \tilde{Q}^{-1} \otimes \tilde{Q}^{-1}$ corresponds to a global trivialisation induced by the function $g_{P_1,P_2}(P_1 + P_2 + \tilde{Q} - \cdot)/g_{P_1,P_2}(\cdot)$.

It follows that the function associated to the cubical representation $[P_1 + \tilde{P}_2, \tilde{Q}; \tilde{0}, P_1 + \tilde{P}_2 + \tilde{Q}]$, is equal to $\frac{g_{P_1,P_2}(P_1+P_2+\tilde{Q}-\cdot)}{g_{P_1,P_2}(\cdot)}g_{P_1,Q}g_{P_2,Q}$. Comparing with Equation (10), we need to check that $g_{P_1,P_2}(P_1 + \tilde{P}_2 + \tilde{Q} - \cdot) = g_{P_1,P_2}(\tilde{Q} + \cdot)$. These two functions have the same divisor (using our assumption that $D$ is symmetric), and their evaluation at a point $T$ such that $2T = P_1 + P_2$ yield the same value $g_{P_1,P_2}(\tilde{Q} + T)$, hence they are equal. We leave the case where $D$ is only linearly symmetric to the reader (we could also invoke flat descent to reduce to the symmetric case). $\square$

**Example 4.17.** If $g_{P,Q} = [\tilde{P}, \tilde{Q}; \tilde{0}, P + \tilde{Q}]$, then $g_{P,Q}^{*1,-1} = [-\tilde{P}, \tilde{Q}; \tilde{0}, -\tilde{P} + \tilde{Q}]$, where $-\tilde{P} + \tilde{Q} = \text{DiffAdd}(-\tilde{P}, \tilde{Q}, P + \tilde{Q})$.

If we have a cubical representation of $g_{P_1,Q}, g_{P_2,Q}$ as above, and also a cubical representation of $g_{P_1,Q} *_1 g_{P_2,Q} : g_{P_1+P_2,Q} = [P_1 + \tilde{P}_2, \tilde{Q}; \tilde{0}, P_1 + \tilde{P}_2 + \tilde{Q}]$, then $g_{P_1-P_2,Q} =$
**Input:** a biextension element $g_{P,Q} = [\tilde{P}, \tilde{Q}, \tilde{\emptyset}, P + Q]$ represented by cubical points

**Output:** cubical points $\ell\tilde{P}, \ell\tilde{P} + Q$ such that $g_{P,Q}^{*1,\ell} = [\ell\tilde{P}, \tilde{Q}, \tilde{\emptyset}, \ell\tilde{P} + Q]$

→ For each bit $b_i$ of $\ell$ from left to right (skipping the first one), given a cubical representation $\widetilde{nP}, n\widetilde{P} + Q$, of $g_{P,Q}^{*1,n}$, where $n$ is the current truncation of $\ell$ on the leftmost bits, do a cubical biextension double:

a. $2n\widetilde{P} + Q = \text{DiffAdd}(n\widetilde{P} + Q, n\widetilde{P}, \tilde{Q})$;

b. $2n\widetilde{P} = \text{Double}(n\widetilde{P})$;

And if $b_i = 1$, also do a cubical biextension addition:

a. Compute $(2n + 1)P = 2(nP) + P$ and take an arbitrary cubical lift $(2n + 1)P$ of $(2n + 1)P$.

b. $(2n + 1)P + Q = \text{ThreeWayAdd}(2n\widetilde{P}, \tilde{P}, \tilde{Q}, P + Q, 2n\widetilde{P} + Q, (2n + 1)P)$;

<caption>ALGORITHM 4.1. Biextension exponentiation via cubical double and add</caption>

$[P_1 - P_2, \tilde{Q}; \tilde{\emptyset}, P_1 - \widetilde{P_2} + Q]$, is a cubical representation of $g_{P_1,Q}^{*1}g_{P_2,Q}^{*1,-1}$, where $P_1 - P_2 = \text{DiffAdd}(\tilde{P}_1, -\widetilde{P_2}, P_1 + \widetilde{P_2})$ and $P_1 - \widetilde{P_2} + Q = \text{DiffAdd}(P_1 + \widetilde{Q}, -\widetilde{P_2}, P_1 + \widetilde{P_2} + \widetilde{Q})$.

By Theorem 4.16, we have two algorithms to compute the biextension exponentiation $g_{P,Q}^{*1,\ell}$ in the cubical representation $g_{P,Q} = [\tilde{P}, \tilde{Q}; \tilde{\emptyset}, P + Q]$. The first one, given in Algorithm 4.1 is a standard double and add algorithm, using standard (cubical) biextension addition, each biextension addition involving one abelian variety addition and one cubical three way addition. We note that by Theorem 4.16, we actually have two ways to compute biextension doubling in a double and add ladder: either we use a biextension normal addition of $g_{P,Q}$ with itself, or we use a cubical biextension differential doubling. In Algorithm 4.1 we use the second method, because it is the faster one for Kummer lines.

The second one is to do a differential ladder, using a cubical differential ladder to compute $\ell\tilde{P}, \ell\tilde{P} + Q$ from $g_{P,Q}$. Namely at each step we have $g_{P,Q}^m, g_{P,Q}^{m+1}$, represented via the cubical points $m\widetilde{P}, m\widetilde{P} + Q, (m + 1)P$ (in theory we would also need $Q + (m + 1)P$ to represent $g_{P,Q}^{m+1}$, but we will see we won't need it in the algorithm; and in any case it could be recomputed on the fly through a three way addition). In other words, we use a biextension ladder, each step involving a cubical biextension differential addition and a cubical biextension doubling (here using a normal cubical biextension doubling would not be correct). Each step of this biextension differential ladder then involves a cubical doubling and two cubical differential additions. (It should involve three cubical differential additions but from the remark above the one to compute the $Q + (m + 1)P$ is not used).

In Algorithm 4.2 we present such a ladder algorithm, except we use a ladder of the form $g_{P,Q}^{m-1}, g_{P,Q}^m$ represented by the points $(m-1)P, m\widetilde{P} + Q, m\widetilde{P}$ instead.

We also need to explain how to work out the action of $A[D]$ on the biextension $X_D$ from Lemma 3.9 via cubical arithmetic. Recall from Section 4.2.6 that we have an action of the theta group $G(D)$ on cubical points.

**Lemma 4.18.** If $g_{P,Q} = [\tilde{P}, \tilde{Q}; \tilde{\emptyset}, P + Q]$ and $T \in A[D]$, then letting $g_T$ be any function such that $(T, g_T) \in G(D)$, $T \cdot g_{P,Q} = [g_T \cdot \tilde{P}, \tilde{Q}; \tilde{\emptyset}, g_T \cdot P + Q] = [P + T, \tilde{Q}; \tilde{\emptyset}, P + \widetilde{Q} + T]$.

4.4. **Pairings via the cubical representation.** Using Section 4.3 to represent biextension elements, by Theorems 3.11 and 4.16 we get the following formulas for pairings:
**Input:** a biextension element $g_{P,Q} = [\tilde{P}, \tilde{Q}; \tilde{0}, P + Q]$ represented by cubical points

**Output:** cubical points $\ell\tilde{P}, \ell\tilde{P} + Q$ such that $g_{P,Q}^{*1,\ell} = [\ell\tilde{P}, \tilde{Q}, \tilde{0}, \ell\tilde{P} + Q]$

→ Compute $2\tilde{P} = \text{Double}(\tilde{P})$, $2\tilde{P} + Q = \text{DiffAdd}(P + Q, \tilde{P}, \tilde{Q})$ to get a representation of $g_{P,Q}^{*1,2}$.

→ For each bit $b_i$ of $\ell - 1$ from left to right (skipping the first one), given a cubical representation $\tilde{nP}, (n+1)P, (n+1)\tilde{P} + Q$ of $g_{P,Q}^{*1,n}, g_{P,Q}^{*1,n+1}$ where $n$ is the current truncation of $\ell - 1$ on the leftmost bits, compute:

a. If $b_i = 0$:

• $(2n+1)\tilde{P} + Q = \text{DiffAdd}((n+1)\tilde{P} + Q, \tilde{nP}, P + Q);$

• $(2n+1)P = \text{DiffAdd}((n+1)P, \tilde{nP}, \tilde{P});$

• $2n\tilde{P} = \text{Double}(\tilde{nP});$

b. If $b_i = 1$:

• $2(n+1)\tilde{P} + Q = \text{DiffAdd}((n+1)\tilde{P} + Q, (n+1)P, \tilde{Q});$

• $2(n+1)P = \text{Double}((n+1)P);$

• $(2n+1)P = \text{DiffAdd}((n+1)P, \tilde{nP}, \tilde{P});$

<caption>ALGORITHM 4.2. Biextension exponentiation via a cubical ladder</caption>

**Theorem 4.19.** Let $g_{P,Q} = [\tilde{P}, \tilde{Q}; \tilde{0}, P + Q]$, and use any of the two cubical biextension exponentiation to get a representation $g_{P,Q}^{*1,\ell} = [\tilde{P}, \tilde{Q}; \tilde{0}, \ell\tilde{P} + Q]$.

Assume that $P \in A[\ell D]$, we can then use the action of $-\ell P$ from Lemma 4.18 to compute $-\ell P \cdot g_{P,Q}^{*1,\ell} = [-\ell P \cdot \ell\tilde{P}, \tilde{Q}; \tilde{0}, -\ell P \cdot \ell\tilde{P} + Q]$. Then $-\ell P \cdot \ell\tilde{P} = \lambda_{0,P}\tilde{0}$, $-\ell P \cdot \ell\tilde{P} + Q = \lambda_{1,P}\tilde{Q}$, so $-\ell P \cdot g_{P,Q}^{*1,\ell} = \lambda_P$ with $\lambda_P = \lambda_{1,P}/\lambda_{0,P}$. We will also denote $\lambda_P = \frac{(-\ell\tilde{P}) \cdot \ell\tilde{P} + Q}{\tilde{Q}} \frac{\tilde{0}}{(-\ell\tilde{P}) \cdot \ell\tilde{P}}$.

If $Q \in A[\ell D]$ too, then the Weil pairing is (up to a sign) $e_{W,D,\ell}(P,Q) = \lambda_P/\lambda_Q$. If $P \in A[\ell D](k), Q \in A(k)$ and our cubical points are rational, the non reduced Tate pairing is (up to a sign) $e_{T,D,\ell}(P,Q) = \lambda_P$.

If $k = \mathbb{F}_q$, $\mu_\ell \subset \mathbb{F}_q$, and $P \in A[\ell]$, we can also recover the reduced Tate pairing by computing $\lambda'_P$ such that $g_{P,Q}^{*1,q-1} = \lambda'_P$, or alternatively such that $g_{P,Q}^{*1,q} = \lambda'_P g_{P,Q}$. We have $\lambda'_P = \frac{(q-1)\tilde{P} + Q}{\tilde{Q}} \frac{\tilde{0}}{(q-1)P} = \frac{q\tilde{P} + Q}{\tilde{P} + Q} \frac{\tilde{Q}}{\tilde{q}\tilde{P}}$.

The same remark as in Remark 2.11 still applies.

**Remark 4.20 (Refined bilinearity).** We can extend Remark 3.14 as follows. Let us assume for simplicity that we are computing the Tate pairing on $\mathbb{G}_1 = E[\ell](\mathbb{F}_q) \times \mathbb{G}_2 \subset E[\ell](\mathbb{F}_{q^d})$, and that $\ell$ is prime to $q-1$, so that $d > 1$ where $d$ is the embedding degree.

Then given $P \in \mathbb{G}_1$, by Section 4.2.5 there is a unique $\mathbb{F}_q$-rational cubical lift $\tilde{P}$ which is $\ell$-periodic, i.e., such that $(a\ell + b)\tilde{P} = b\tilde{P}$ for all $a, b \in \mathbb{Z}$ (we will come back to these canonical cubical points of $\ell$-torsion in Sections 6.2 and 6.4).

To compute the Tate pairing $e_{T,\ell}(P,Q)$ with $Q \in \mathbb{G}_2$ (or even any point in $E[\ell](\mathbb{F}_{q^d})$, we can start with $\tilde{P}$ as above and an arbitrary choice of $\tilde{Q}, P + Q$. Since $\ell\tilde{P} = \tilde{0}$, the (non reduced) Tate pairing is given by the monodromy $e_{T,\ell}(P,Q) = \lambda_P \in \mathbb{F}_{q^d}^*$ with $\ell\tilde{P} + Q = \lambda_P\tilde{Q}$. If we look at the associated biextension elements, we have $g_{P,Q}^{*1,\ell} = \lambda_P$, so $g_{P,Q}^{*1,\ell+1} = \lambda_P g_{P,Q}$, hence since $\ell\tilde{P} + P = \tilde{P}$ by assumption on $\tilde{P}$, we can also recover $\lambda_P$ as $\ell P + \tilde{P} + Q = \lambda_P P + Q$.
Now by Example 4.10 (beware of the change of notations), we have $\ell u_0 P + \widetilde{u_1} P + vQ = \lambda_P^{u_0 v} u_1 \widetilde{P} + vQ$. In particular, to compute the Tate pairing $e_{T,\ell}(iP, Q)$ (resp. $e_{T,\ell}(P, iQ)$), if we start with $\widetilde{Q}, i\widetilde{P} + Q$ (resp. $i\widetilde{Q}, P + iQ$) as computed from $\widetilde{P}, \widetilde{Q}, P + Q$ by the cubical arithmetic, then we have $\ell i\widetilde{P} + Q = \lambda_P^i \widetilde{Q}$ (resp. $\ell P + iQ = \lambda_P^i i\widetilde{Q}$).

As in Porisms 2.10 and 3.10 we get:

**Porism 4.21.** Let $g_{P,Q} = [\widetilde{P}, \widetilde{Q}; \tilde{0}, P + Q]$, and use any of the two cubical biextension exponentiation to get a representation $g_{P,Q}^{*1,\ell} = [\widetilde{\ell P}, \widetilde{Q}; \tilde{0}, \ell P + Q]$.

Then the function $f_{\ell,P}$ evaluated on the cycle $(x+Q)-(x)$ is given by $\frac{g_{\ell P,Q}}{g_{P,Q}^{\ell}}$.

If furthermore $P \in A[\ell D]$, then $f_{-\ell D_P}((R+Q)-(R)) = \frac{(-\ell P) \cdot \ell P + Q + R\widetilde{R}}{(-\ell P) \cdot \ell P + R\widetilde{Q} + R} \left( \frac{\widetilde{P} + R\widetilde{Q} + R}{P + Q + R\widetilde{R}} \right)^{\ell}$.

Here $\frac{\widetilde{P}+R\widetilde{Q}+R}{P+Q+R\widetilde{R}}$ is not a monodromy information but a notation for the theta group function $g_{P,Q}$ represented by $\widetilde{P}, \widetilde{Q}$ evaluated at $R$; we refer to Section 4.5.2 and Equation (17) for more details.

We have a natural Galois action on cubical points: if $\sigma$ is a Galois group element, $\sigma(\widetilde{P})$ is the rigidification of our rational line bundle $\mathcal{L}$ at $\sigma(P)$ given by applying $\sigma$ to the rigidification of $\mathcal{L}$ at $P$.

In the context of the Ate and optimal Ate pairings, Proposition 3.17 and Corollary 3.19 then become:

**Proposition 4.22** (Ate and optimal Ate pairings in the cubical representation). Let $A/\mathbb{F}_q$ be an abelian variety with embedding degree $d > 1$ with respect to $\ell$: $\mu_\ell \subset \mathbb{F}_{q^d}$. Let $\mathbb{G}_1, \mathbb{G}_2$ denotes the subspace of $A[\ell]$ where the Frobenius $\pi_q$ has eigenvalues 1 and $q$ respectively. Let $P \in \mathbb{G}_2$ and $Q \in \mathbb{G}_1$. Take any cubical biextension representation $(P,Q,g_{P,Q}) = [\widetilde{P}, \widetilde{Q}; \tilde{0}, P + Q]$. Let $\lambda \equiv q \mod \ell$.

Then $(P,Q,g_{P,Q})^{*1,\lambda} = [\lambda\widetilde{P}, \widetilde{Q}; \tilde{0}, \lambda\widetilde{P} + Q]$ and $\pi_q((P,Q,g_{P,Q})) = [\pi_q(\widetilde{P}), \pi_q(\widetilde{Q}); \pi_q(\tilde{0}), \pi_q(\widetilde{P} + Q)]$ both represent biextension elements above $(qP,Q)$. They differ by a monodromy constant which gives the (non reduced, except if $\lambda = q$) $\lambda$-Ate pairing.

Explicitly, assuming that $\widetilde{Q}, \tilde{0}$ are chosen to be $\mathbb{F}_q$-rational for simplicity,

$$a_{\lambda,\ell}(P,Q) = \frac{q\widetilde{P} + Q}{\pi_q(\widetilde{P})} \frac{\pi_q(\widetilde{P})}{q\widetilde{P}}.$$

If $\ell = \sum c_i q^i$, we can compute two cubical points $\ell\widetilde{P} + Q, \ell\widetilde{P}$ as follows:

(1) Compute the $c_i \widetilde{P} + Q, c_i \widetilde{P}$ via a cubical biextension exponentiation;

(2) Compute $c_i q^i \widetilde{P} + Q, c_i q^i \widetilde{P}$ by applying $\pi_q^i$ to $c_i \widetilde{P} + Q, c_i \widetilde{P}$;

(3) Compute iteratively $Q + c_i q^i \widetilde{P} + \sum_j c_j q^j \widetilde{P}, c_i q^i \widetilde{P} + \sum_j c_j q^j \widetilde{P}$ by taking an arbitrary choice for $c_i q^i \widetilde{P} + \sum_j c_j q^j \widetilde{P}$ and then using a cubical three way addition to compute $Q + c_i q^i \widetilde{P} + \sum_j c_j q^j \widetilde{P}$ from $\widetilde{Q}, c_i q^i \widetilde{P}, \sum_j c_j q^j \widetilde{P}$ and the two by two sums $c_i q^i \widetilde{P} + \sum_j c_j q^j \widetilde{P}, Q + c_i q^i \widetilde{P}, Q + \sum_j c_j q^j \widetilde{P}$.

Then $[\ell\widetilde{P}, \widetilde{Q}; \tilde{0}, \ell\widetilde{P} + Q]$ is a biextension element above $(0,Q)$, hence represents a constant equal to $\frac{\ell\widetilde{P} + Q}{\tilde{0}}$ which is the optimal Ate pairing.
**Remark 4.23** (Cubical arithmetic versus biextension arithmetic). The cubical arithmetic is a refinement of the biextension arithmetic, since we can recover the biextension arithmetic from it. On the other hand, since for pairings we only need the biextension arithmetic, and different cubical points can represent the same biextension points by Lemma 4.15, we have some leeways: even if we don't compute the correct cubical arithmetic, as long as the underlying biextension arithmetic is still correct, our pairings will be correct.

We have seen an example already when using the cubical biextension double and add to compute $g_{P,Q}^{*1,l}$. The points $\ell\tilde{P}, \ell\tilde{P}+Q$ we obtain in this way are not the correct one from the cubical point of view, but they differ from the correct ones by the same factor $\lambda$, which mean that the associated biextension element is still the correct one by Lemma 4.15.

An important example of the difference between the two arithmetic is with respect to the multiplication by elements $\lambda \in k$. In the biextension (or theta groups), we have $(\lambda \cdot g_{P,Q})^{*1,l} = \lambda^l \cdot g_{P,Q}^{*1,l}$. By contrast, we have $\ell(\lambda \cdot \tilde{P}) = \lambda^{l2}\tilde{P}$.

One can use Lemma 4.5 to check directly that the Weil pairing and the class of the non reduced Tate pairing as computed in Theorem 4.19 does not depends on the choice of $\tilde{P}, \tilde{Q}, P+Q$. We can also use that $\lambda \cdot [\tilde{P}, \tilde{Q}; P+Q] = [\tilde{P}, \tilde{Q}; \tilde{0}, \lambda P+Q]$ to recover that $g_{P,Q}^{*1,l} = \lambda^l \cdot g_{P,Q}^{*1,l}$.

Finally we remark that there are two special cases where we can do a biextension exponentiation faster using the cubical arithmetic.

The first one is when $l = 2^m$, in which case the biextension exponentiation consists entirely of biextension doublings, so we can use a cubical biextension ladder consisting entirely of cubical biextension doublings, i.e. a cubical doubling and a cubical differential addition at each step.

The other more subtle case is for self pairings, i.e. when we want to compute $g_{P,P}^{*1,l}$. Since we are allowed to choose any $g_{P,P}$ above $(P,P)$ for pairings, we will take one of special form, given by $[\tilde{P}, \tilde{P}, \tilde{0}, 2\tilde{P}]$. In other words, we take for $2\tilde{P}$ the cubical doubling $2\tilde{P}$ rather than an arbitrary cubical points. Changing $\tilde{P}$ to $\lambda \cdot \tilde{P}$ changes $2\tilde{P}$ to $\lambda^4 \cdot 2\tilde{P}$, hence $g_{P,P}$ to $\lambda^2 \cdot g_{P,P}$. In other words, these special $g_{P,P}$ form a torsor under the squared action of $G_m$ rather than under $G_m$. Then we can compute $\ell\tilde{P}, (\ell+1)\tilde{P}$ via a cubical ladder, which involves one cubical doubling and one cubical differential addition by step, to get $g_{P,P}^{*1,l} = [\tilde{P}, \ell\tilde{P}, \tilde{0}, (\ell+1)\tilde{P}]$. Here it is important to use the cubical arithmetic.

A last remark is that when using the cubical representation to compute different pairings $e(P, Q_i)$ with the same base point $P$, i.e. biextension exponentiation of elements of the form $g_{P,Q_i} = [\tilde{P}, \tilde{Q}_i; \tilde{0}, P+Q_i]$, then for the representation of each $g_{P,Q_i}^{*1,l} = [\ell\tilde{P}, \tilde{Q}_i; \tilde{0}, \ell P+Q_i]$, we can of course use the same $\ell\tilde{P}$ and share the computation. This is also a well known pairing trick.

**4.5. The affine lift representation of cubical points.** To use the cubical arithmetic in order to obtain the biextension arithmetic in order to obtain our pairings, we need to find a convenient representation of our cubical points $\tilde{P}$.

**4.5.1. Cubical coordinates.** In this section we introduce cubical coordinates for cubical points, which we also call the affine coordinates representation (or affine representation for short) because it lifts the projective representation of abelian varieties points. Fix $X_1, \dots, X_m \in \Gamma(\mathcal{L})$ global sections of $\mathcal{L} = O_A(D)$. We have a partial map $\varphi: A \to \mathbb{P}^{m-1}, P \mapsto (X_1(P), \dots, X_m(P))$, which is not defined at the base points of $\mathcal{L}$.
The element $X_i(P)$ is in the fiber $\mathcal{L}(P)$ of the line bundle $\mathcal{L}$, and $\tilde{P}$ gives a rigidification $O_A(P) = \kappa(P) \to \mathcal{L}(P)$. Using this isomorphism, we obtain an element $X_i(\tilde{P}) \in \kappa(P)$. This allows to interpret $X_i$ as an affine coordinate on cubical points.

More explicitly, our cubical point $\tilde{P}$ can be lifted to a local trivialisation $\phi_P$ of $\mathcal{L}$ at $P$, which is the same as a choice of a local generator $s$ at $P$. So we can write $X_i = s_i \cdot s$, for some $s_i \in O_A$. We define the affine representation of our cubical point to be $\tilde{\phi}(\tilde{P}) = (X_1(\tilde{P}), X_m(\tilde{P})) := (s_1(P), \dots, s_m(P)) \in \mathbb{A}^m$; it is easy to check that it depends only on $\tilde{P}$. If $P$ is not a base point, $\tilde{\phi}(\tilde{P})$ is an affine point lying above the projective point $\phi(P)$. Furthermore, in this case not all $s_i(P)$ are 0, and our local section $s$ is completely determined from any non zero coordinate of $\tilde{\phi}(\tilde{P})$: $\tilde{P}$ is completely determined by $(P, \tilde{\phi}(\tilde{P}))$, or even by $(P, X_i(\tilde{P}))$ for any $i$ such that $s_i(P) \neq 0$. If furthermore $\mathcal{L}$ is very ample, $P$ is completely determined by $\phi(P)$, so $\tilde{P}$ is completely determined by $\tilde{\phi}(\tilde{P})$, in which case we will often denote it by $\tilde{P}$ too.

We thus obtain a convenient representation as affine points of the cubical points. For instance, in Theorem 4.19, the value $\lambda_{1,P}$ is simply given as $\lambda_{1,P} = X_i(\ell\tilde{P} + \tilde{Q})/X_i(\tilde{Q})$ for any $i$ such that $X_i(\tilde{Q}) \neq 0$. Furthermore, if $\tilde{P}$ is represented by $(X_1(\tilde{P}), \dots, X_m(\tilde{P}))$, the Galois action $\sigma(\tilde{P})$ of a Galois element $\sigma$ on the rigidification $\tilde{P}$ of $\mathcal{L}$ at $P$ is given by $\sigma(\tilde{P}) = (\sigma(X_1(\tilde{P})), \dots, \sigma(X_m(\tilde{P})))$. If $P \in A[\mathcal{L}]$, and $(P, g_P) \in G(\mathcal{L})$ is an element of the theta group above $P$, then the action of the theta group element $g_P$ on $\tilde{P}$ is given by $g_P \cdot \tilde{P} = ((g_P \cdot X_1)(\tilde{P}), \dots, (g_P \cdot X_m)(\tilde{P}))$ where $g_P \cdot X_i$ is the natural action of $G(\mathcal{L})$ on sections $X_i \in \Gamma(\mathcal{L})$ from Equation (2).

We will call the cubical doublings, differential additions and three way additions in the affine lift representation of cubical points the affine doublings, affine differential additions and affine three way additions respectively.

**Remark 4.24.** There is a global $\mathbb{G}_m$-ambiguity when using affine coordinates $X_i$ to represent cubical points. We'll illustrate this in the case of an elliptic curve: take a short Weierstrass equation $y^2 = x^3 + ax + b$, with associated Weierstrass coordinates $x, y$. The projective equation is $Y^2Z = X^3 + aXZ^2 + bZ^3$, and fixing the coordinate $Z \in \Gamma(3(0_E))$ fixes $X, Y$ via $X = xZ, Y = yZ$. However, the projective curve equation does not change if we replace $Z$ by $\lambda Z$, so we could also work with $\lambda X, \lambda Y, \lambda Z$. Now, via the affine representation of cubical points by the coordiantes $X, Y, Z$, there is no difference between keeping the same cubical points and changing the coordinates $X, Y, Z$ to $\lambda X, \lambda Y, \lambda Z$, or keeping the same coordinates $X, Y, Z$ and changing all cubical points $\tilde{P}$ into $\lambda \tilde{P}$.

Let $\mathcal{L} = O_E((0_E))$ be the line bundle associated to the canonical principal polarisation on $E$. We will often say that we normalize $\tilde{0}$ so that $(Z/(x/y))(\tilde{0}) = 1$. This means that if we lift $\tilde{0}$ to a local trivialisation of $\mathcal{L}$ at $0_E$, i.e. a local choice of section $s$; the section $Z \in \Gamma(\mathcal{L})$ can then be written locally as $Z = gs$ for some function $g \in k(E)$, and we require that $(g/(x/y))(\tilde{0}) = 1$. We can thus interpret this normalisation condition in two different ways: the first one is to fix a global section $Z$, and then ask to take $\tilde{0}$ such that $(Z/(x/y))(\tilde{0}) = 1$; the second one is to fix $\tilde{0}$ first and then take $Z$ such that we have this same equality.

### 4.5.2. Cubical functions for pairings computations.
Let $[\tilde{P}_1, \tilde{P}_2, \tilde{P}_3, \tilde{P}_4; \tilde{Q}_1, \tilde{Q}_2, \tilde{Q}_3, \tilde{Q}_4]$ be cubical points in Riemann relation. By definition and Proposition 4.1 they define a canonical function $\gamma$, which only depends on $[P_1, P_2, P_3, P_4; Q_1, Q_2, Q_3, Q_4]$.

We can recover $\gamma$ in terms of the affine coordinates $X_i$ as follows. Let $D_i$ be the divisor of zeroes of $X_i$; since $X_i \in \Gamma(\mathcal{L})$ is a global section, the associated line bundle $O_A(D_i)$ is isomorphic to $\mathcal{L}$ and all the $D_i$ are linearly equivalent. Since the points $[P_1, P_2, P_3, P_4; Q_1, Q_2, Q_3, Q_4]$.
are in Riemann position, they define canonical functions $\gamma_i$ for each $i$. And we have, by definition of the affine coordinates, $\gamma_i(0) = \frac{X_i(\tilde{P}_1)X_i(\tilde{P}_2)X_i(\tilde{P}_3)X_i(\tilde{P}_4)}{X_i(\tilde{Q}_1)X_i(\tilde{Q}_2)X_i(\tilde{Q}_3)X_i(\tilde{Q}_4)}$.

Take $R \in A$, and consider the points $[P_1+R, \tilde{P}_2+R, P_3+R, P_4+R; Q_1+R, Q_2+R, Q_3+R, Q_4+R]$, they are still in Riemann position, and the associated function is simply $t_R^*\gamma_i$. So if $[P_1+R, P_2+R, P_3+R, P_4+R; Q_1+R, Q_2+R, Q_3+R, Q_4+R]$ are in Riemann position, we obtain:

$$\gamma_i(R) = \frac{X_i(P_1+R)X_i(P_2+R)X_i(P_3+R)X_i(P_4+R)}{X_i(Q_1+R)X_i(Q_2+R)X_i(Q_3+R)X_i(Q_4+R)}$$

We can go further: fix cubical points $\tilde{P}, \tilde{Q}, P+Q$, since the cycle $Z = (P+Q) + (0)-(P)-(Q)$ satisfy $s(Z) = 0$, these cubical points defines uniquely a function $f_Z$ as in Section 4.2.7, which in this case is a biextension element $g_{P,Q} \in X_\mathcal{L}$ in the biextension associated to $\mathcal{L}$.

To each coordinate $X_i$, with zero divisor $D_i$, we let $g_{i,P,Q}$ be the function with divisor $D_{i,P+Q} - D_{i,P} - D_{i,Q}$ associated to $g_{P,Q}$ via the isomorphism $X_\mathcal{L} \simeq X_{D_i}$.

If $R \in A$, we can fix arbitrary cubical points $\tilde{R}, R+P, R+Q$, and look at the unique cubical point $R+\tilde{P}+Q$ given by the three way addition, i.e. such that $[R+\tilde{P}+Q, \tilde{R}, \tilde{P}, \tilde{Q}; \tilde{\emptyset}, P+\tilde{Q}, R+\tilde{Q}, P+\tilde{Q}]$ are in Riemann position. By Theorem 4.16 combined with the same reasoning as above, we have

$$(17) \qquad g_{i,P,Q}(R) = \frac{X_i(P+\tilde{Q}+R)X_i(\tilde{R})}{X_i(P+R)X_i(\tilde{Q}+R)},$$

and so

$$g_{i,P,Q}((R) - (0)) = \frac{X_i(P + \tilde{Q} + R)X_i(\tilde{R})X_i(\tilde{P})X_i(\tilde{Q})}{X_i(P + R)X_i(\tilde{Q} + R)X_i(P + \tilde{Q})X_i(\tilde{Q})}.$$

In particular, $g_{i,P,Q}$ does not depend on the choice of $\tilde{R}, R+P, R+Q$, as long as $R+\tilde{P}+Q$ is computed through a three way addition, as can be checked directly by homogeneity.

This allows to write the genuine function $g_{i,P,Q}$ as a product of “cubical functions”.

If $T \in A[D_i]$, we have also seen in Section 4.2 how a choice of cubical point $\tilde{T}$ gives a canonical theta group element $(T, g_{i,T}) \in G(D_i)$. It can be described as follows: if $R \in A$, take an arbitrary cubical point $\tilde{R}$, and let $\tilde{R}+T$ be given by the action of $\tilde{T}$ on $\tilde{R}$. Then by definition of this action, $g_{i,T}(R) = X_i(\tilde{R}+\tilde{T})/X_i(\tilde{R})$.

For a degree 0 cycle $Z$ such that $s(Z) \in \text{Ker } \Phi_\mathcal{L}$, and a cubical lift $\tilde{Z}$ of $Z$, we can combine the two methods to iteratively reduce $\tilde{Z}$ to a cycle $s(Z) - \tilde{\emptyset}$ and express the function $f_{\tilde{Z}}$ as product of cubical functions.

**4.5.3. The affine cubical biextension representation as evaluation of cubical functions.** Let $(P, Q, g_{P,Q}) \in X_D$ be a biextension element. In the evaluation representation, we represent $g_{P,Q}$ via (the extended value) $g_{P,Q}(0)$ at the base point 0. Let $X_1, \dots, X_m \in \Gamma(D)$, and assume that $X_1$ has $D$ for divisor of zeroes, $X_i$ has $D_i$ for divisor of zeroes, with $D_i = D+\text{div}(X_i/X_1)$. We have a function $g_{i,P,Q} = g_{P,Q} \frac{X_i}{X_1}((\cdot+P+Q)(\cdot)-(\cdot+P)-(\cdot+Q))$ coming from the biextension isomorphism $X_D \simeq X_{D_i}$ (see Remark 3.8). We can then define a multidevaluation representation, representing $g_{P,Q}$ via the (extended) evaluations $g_{i,P,Q}(0)$. It is often the case that the functions $X_i$ are determined from $X_1$ via translation by some elements of torsion $T$ (or more precisely via the action of some $(T, g_T) \in G(D)$ on $X_1$ in the theta group). This is for instance the case for theta functions of level $n$ (where the $T$ are points of $n$-torsion), or for the Montgomery model of the Kummer line where $T = (0:1)$ and
$g_T \cdot (X, Z) = (Z, X)$. In this case the multievaluation representation is simply the evaluation of $g_{P,Q}$ not only at the base point $R_0 = 0$, but also at the points $R_0 + T$.

Now assume that we are given a cubical representation $g_{P,Q} = [\tilde{P}, \tilde{Q}; \tilde{0}, P + \tilde{Q}]$. By Section 4.5.2, given $R \in A$, and any choice of $\tilde{R}$ above $R, R + P, R + \tilde{Q}$, computing $P + \tilde{Q} + R$ via a cubical three way add, we have

$$ (18) \qquad g_{i,P,Q} : R \mapsto \frac{X_i(P + \tilde{Q} + R)X_i(\tilde{R})}{X_i(P + \tilde{R})X_i(\tilde{Q} + R)}. $$

Now, although the function $g_{i,P,Q}$ is a genuine function on our abelian variety, its individual members $\tilde{R} \mapsto X_i(P + \tilde{Q} + R)$, $X_i(\tilde{R})$, $X_i(P + \tilde{R})$, $X_i(\tilde{Q} + R)$ only make sense as virtual cubical functions, whose associated divisor of zeroes are $t_{P+\tilde{Q}}^*D_i$, $D_i$, $t_P^*D_i$ and $t_Q^*D_i$ respectively. And the affine cubical representation is precisely the evaluation of these virtual functions at 0.

When doing a biextension exponentiation to compute $g_{P,Q}^{*1,\ell}$, in the multievaluation representation we obtain functions $g_{i,\ell P,Q}$ such that by Porism 3.10 $g_{i,\ell P,Q}/g_{i,P,Q}^\ell$ is the function $f_{i,\ell P}$ evaluated on the cycle $(x+Q)-(x)$, where $f_{i,\ell P}$ has for divisor $D_{i,\ell P} + (\ell-1)D_i - \ell D_{i,P}$. The multievaluation representation is given by the evaluation of the functions $g_{i,\ell P,Q}$ at 0, and so $g_{i,\ell P,Q}(0)/g_{i,P,Q}^\ell(0)$ is the value of $f_{i,\ell P}$ at the cycle $(Q)-(0)$.

Now, the cubical representation also allows to write

$$ (19) \qquad g_{i,\ell P,Q}(R) = \frac{X_i(\ell P + \tilde{Q} + R)X_i(\tilde{R})}{X_i(\ell \tilde{P} + R)X_i(\tilde{Q} + R)}. $$

In particular, we have that the evaluation of $f_{i,\ell P}$ at the cycle $(R+Q)-(R)$ is given by

$$ (20) \qquad \frac{X_i(\ell P + \tilde{Q} + R)X_i(\tilde{R})}{X_i(\ell \tilde{P} + R)X_i(\tilde{Q} + R)} \left( \frac{X_i(P + \tilde{R})X_i(\tilde{Q} + R)}{X_i(P + \tilde{Q} + R)X_i(\tilde{R})} \right)^{\ell}, $$

(compare with Example 4.29) and if $P \in A[\ell D]$, and $\ell \tilde{P}$ is an arbitrary cubical point above $\ell P$,

$$ (21) \qquad f_{\ell D_{i,P}}((R+Q)-(R)) = \frac{X_i(-\ell \tilde{P} \cdot \ell P + \tilde{Q} + R)X_i(\tilde{R})}{X_i(-\ell \tilde{P} \cdot \ell \tilde{P} + R)X_i(\tilde{Q} + R)} \left( \frac{X_i(P + \tilde{R})X_i(\tilde{Q} + R)}{X_i(P + \tilde{Q} + R)X_i(\tilde{R})} \right)^{\ell}. $$

And, although the function $g_{i,\ell P,Q}$ is a genuine function on our abelian variety, its individual members $(\tilde{R}, \tilde{P} + \tilde{R}, \tilde{Q} + \tilde{R}) \mapsto X_i(\ell P + \tilde{Q} + \tilde{R})$, $X_i(\tilde{R})$, $X_i(\ell \tilde{P} + \tilde{R})$, $X_i(\tilde{Q} + \tilde{R})$ only make sense as cubical functions, with divisors of zeroes given by $t_{\ell P+\tilde{Q}}^*D_i$, $D_i$, $t_{\ell P}^*D_i$ and $t_Q^*D_i$ respectively.

Thus the cubical representation is a way to decompose the functions $g_{i,\ell P,Q}$ as a product of cubical functions, and the affine lift representation is simply the evaluation of these cubical functions at the cubical point $\tilde{0}$, hence is a way to decompose the functions evaluations $g_{i,\ell P,Q}(0)$ as a product of cubical evaluations.

And Porism 4.21 shows that the cubical arithmetic is an efficient way to embed the Miller functions $f_{\ell P}$ in the affine coordinates of $\ell \tilde{P}$, $\ell \tilde{P} + \tilde{Q}$. Explicitly, evaluating Equations (20) and (21) at $\tilde{0}$:

**Porism 4.25.** Let $D_i$ be the divisor of zeroes of $X_i$ (since $X_i$ is a section of $D$, $D_i \sim D$).
Let $f_{i,\ell,P}$ be a function with divisor $D_{i,\ell P} - \ell D_{i,p}$. Then the function $f_{i,\ell,P}$ evaluated on the cycle $(Q) - (0)$ is given by
$$ \frac{X_i(\ell \overline{P} + Q) X_i(\tilde{\Omega})}{X_i(\ell \overline{P}) X_i(\tilde{\Omega})} \left( \frac{X_i(\tilde{P}) X_i(\tilde{\Omega})}{X_i(\overline{P} + Q) X_i(\tilde{\Omega})} \right)^{\ell}. $$

$$ \text{If } P \in A[\ell D], f_{\ell D_{i,P}}((Q) - (0)) = \frac{X_i(-\ell \overline{P} \cdot \ell \overline{P} + Q) X_i(\tilde{\Omega})}{X_i(-\ell \overline{P} \cdot \ell \overline{P}) X_i(\tilde{\Omega})} \left( \frac{X_i(\tilde{P}) X_i(\tilde{\Omega})}{X_i(\overline{P} + Q) X_i(\tilde{\Omega})} \right)^{\ell}. $$

**Remark 4.26** (Cubical coordinates for monodromy). In Theorem 4.19, we compute $\lambda_P = \frac{(-\ell \overline{P}) \cdot \ell \overline{P} + Q}{\tilde{\Omega} \cdot (-\ell \overline{P}) \cdot \overline{P}}$, which is a quotient of two monodromy information: $-\ell \overline{P} \cdot \ell \overline{P} = \lambda_{0,P} \tilde{\Omega}$, $-\ell \overline{P} \cdot \ell \overline{P} + Q = \lambda_{1,P} \tilde{\Omega}$, $\lambda_P = \lambda_{1,P} / \lambda_{0,P}$.

We can use different cubical coordinates to compute these two monodromy informations; if for instance $X_0(0) \neq 0$ and $X_1(Q) \neq 0$, we have:

$$ \lambda_P = \frac{X_1((-\ell \overline{P}) \cdot \ell \overline{P} + Q)}{X_1(\tilde{\Omega})} \frac{X_0(\tilde{\Omega})}{X_0((-\ell \overline{P}) \cdot \ell \overline{P})}. $$

**Remark 4.27.** When using Porism 4.25 and Theorem 4.19 to evaluate the extended Tate pairing as in Remark 2.11 when $D = mD_1$, one need to be careful about the choice of the coordinate $X_i$.

Indeed, using $X_i$ amount to computing the extended Tate pairing associated to $D_i$, but we have seen in Remark 2.11 that for the extended Tate pairing we need to be sure to choose $D_i$ such that $D_i = mD'_1$, with $D'_1$ rational. This won't be the case in general for the zero divisor $D'$ of an arbitrary section $X \in \Gamma(O_A(D))$.

On the other hand, if $X_1$ has zero divisor $D = mD_1$, then we have seen in Remark 2.11 that we do not need to use the correcting factor $g_{P,Q}^{\ell}$ to correct the monodromy information $\lambda_P$ when $g_{P,Q}$ comes from a $m$-th tensor power of a rational biextension element in $X_{D_1}$. An easy way to ensure this is to start with $g_{P,Q} = [\tilde{P}, \tilde{Q}, \tilde{R}, P + Q, P + R, Q + R]$. Then if $g_{P,Q} \in X_D$ is the biextension function with divisor $D_{P+Q} - D_P - D_Q$ encoded by $[\tilde{P}, \tilde{Q}, \tilde{\Omega}, \tilde{P} + Q]$, we have

$$ g_{P,Q}(R) = \frac{X(P + \tilde{Q} + R)X(\tilde{R})}{X(P + R)X(\tilde{Q} + R)}, $$

where $P + \tilde{Q} + R$ is given by the cubical three way addition.

Using the cubical arithmetic to compute $\ell \tilde{P}, \ell P + \tilde{Q} + R, \ell \overline{P} + R$, if $g_{\ell P,Q} = g_{P,Q}^{*1,\ell}$, we also have

$$ g_{\ell P, Q}(R) = \frac{X(\ell P + \tilde{Q} + R)X(\tilde{R})}{X(\ell \overline{P} + R)X(\tilde{Q} + R)}. $$
**Input:** $P, Q \in A[\ell D]$

**Output:** The Weil pairing $e_{W,\ell D}(P, Q)$

→ Take arbitrary affine cubical lifts $\tilde{P}, \tilde{Q}, P + \tilde{Q}$ of $P, Q, P + Q$ (along with a choice of $\tilde{0}$).

→ Use Algorithm 4.2 or Algorithm 4.1 to compute $\ell \tilde{P} + \tilde{Q}, \ell \tilde{P}$.

→ Take an arbitrary lift $-\ell \tilde{P}$, and compute the theta group action $-\ell \tilde{P} \cdot \ell \tilde{P} + \tilde{Q}, -\ell \tilde{P} \cdot \ell \tilde{P}$.

→ Compute the monodromy $-\ell \tilde{P} \cdot \ell \tilde{P} + \tilde{Q} = \lambda_{1,P}\tilde{Q}, -\ell \tilde{P} \cdot \ell \tilde{P} = \lambda_{0,P}\tilde{0}$.

→ Similarly, compute the monodromy $-\ell \tilde{Q} \cdot \ell \tilde{Q} + P = \lambda_{1,Q}\tilde{P}, -\ell \tilde{Q} \cdot \ell \tilde{Q} = \lambda_{0,Q}\tilde{0}$.

→ Return $e_{\ell D}(P, Q) = \frac{\lambda_{1,P} \lambda_{0,Q}}{\lambda_{0,P} \lambda_{1,Q}}$

<caption>ALGORITHM 4.3. Weil pairing via cubical arithmetic</caption>

And the function

$$f_{\ell,P}(R) = \frac{X(\ell \tilde{P} + R) X(\tilde{R})^{\ell-1}}{X(\tilde{P} + R)^{\ell}}$$

has for divisor $D_{\ell P} - \ell D_P$.

All these functions only depend on $\tilde{P}, \tilde{Q}, \tilde{P} + \tilde{Q}$, not on the choices of $\tilde{R}, \tilde{P} + \tilde{R}, \tilde{Q} + \tilde{R}$.

If $P \in A[\ell D]$ and $f_{\ell D_P}$ is any function with divisor $\ell D_P$, fixing a cubical point $-\ell \tilde{P}$, we have

$$f_{\ell D_P}((Q+R)-(R)) = \frac{X(-\ell \tilde{P} \cdot \ell P + \tilde{Q} + R)}{X(\tilde{Q} + R)} \frac{X(\tilde{R})}{X(-\ell \tilde{P} \cdot \ell \tilde{P} + R)} \left( \frac{X(\tilde{P}) X(\tilde{Q})}{X(P + \tilde{Q} + R) X(\tilde{R})} \right)^{\ell};$$

this does not depend on any choice of cubical points.

If $D = mD_1$, $P \in A[\ell D](\mathbb{F}_q)$, $Q \in A(\mathbb{F}_q)$, the Tate pairing is given by $e_{T,\ell m D_1}(P, Q) = f_{\ell D_P}((Q + R) - (R))$ for any $R \in A(\mathbb{F}_q)$.

If $D = mD_1$, $P, Q \in A[\ell D]$, the Tate pairing is given by $e_{W,\ell m D_1}(P, Q) = \frac{f_{\ell D_P}((Q+R)-(R))}{f_{\ell D_Q}((Q+R)-(R))}$ for any $R \in A$.

Theorem 4.28 give Algorithms 4.3 to 4.6 for the Weil pairing, the Tate pairing, the Ate pairing and the optimal Ate pairing respectively.

For the Weil and Tate pairing we treat the general case on how, when $D = mD_1$, we can use the theta group action of $G(D)$ to recover the pairings of level $\ell m$ with respect to $D_1$ while working with the cubical arithmetic for $D_1$.

For the Ate and optimal Ate pairing we describe the easier case $P \in \mathbb{G}_2 \subset A[\ell];$ but we could use the functions constructed in Theorem 4.28 to treat the general case too. In practice the Ate and optimal Ate pairings are usual for $\ell$ odd, and for pairings in the Montgomery model we have $D = 2(0_E)$ so $m = 2$ is prime to $\ell$, so there is no need to treat this general case.

4.5.4. The naturality of cubical arithmetic. We can give the following philosophical motivation for using the affine representation to compute pairings. By Theorem 4.19, we need to compute cubical points of the form $\ell \tilde{P}, \ell \tilde{P} + \tilde{Q}$. In particular, we need to compute the standard points $\ell P, \ell P + \tilde{Q}$. For this last computation, we want to use projective coordinates to avoid divisions. But for the algorithm, the way we represent the projective coordinates $(X_1 : \dots : X_m)$ is via affine coordinates $(X_1, \dots, X_m)$ anyway. If the way we do the projective arithmetic in terms of affine coordinates is already close to the cubical arithmetic, we can
**Input:** $P \in A[\ell D](\mathbb{F}_q), Q \in A(\mathbb{F}_q), X \in \Gamma(D)$ with divisor of zeroes equal to $mD_1$

**Output:** The non reduced Tate pairing of level $\ell m e_{T, \ell m D_1}(P, Q)$

→ Take arbitrary rational affine cubical lifts $\tilde{P}, \tilde{Q}, \overline{P+Q}$ of $P, Q, P+Q$ (along with a choice of $\tilde{0}$).

→ Use Algorithm 4.2 or Algorithm 4.1 to compute $\ell \overline{P+Q}, \ell \tilde{P}$.

→ Take an arbitrary lift $-\ell \tilde{P}$, and compute the theta group action $-\ell \tilde{P} \cdot \ell \overline{P+Q}, -\ell \tilde{P} \cdot \ell \tilde{P}$.

→ Compute the monodromy $-\ell \tilde{P} \cdot \ell \overline{P+Q} = \lambda_{1,P} \tilde{Q}, -\ell \tilde{P} \cdot \ell \tilde{P} = \lambda_{0,P} \tilde{0}$.

→ Return $e_{\ell m D_1}(P, Q) = \frac{X(\tilde{P})X(\tilde{Q})}{X(\tilde{0})X(\overline{P+Q})} \frac{\lambda_{1,P}}{\lambda_{0,P}}$

ALGORITHM 4.4. Tate pairing via cubical arithmetic

**Input:** $P \in \mathbb{G}_2, Q \in \mathbb{G}_1, \lambda \equiv q \bmod \ell$

**Output:** The non reduced Ate pairing (of level $m$) $a_{\lambda, \ell}(P, Q)$

→ Take arbitrary rational affine cubical lifts of level $m \tilde{P}, \tilde{Q}, \overline{P+Q}$ of $P, Q, P+Q$ (along with a choice of $\tilde{0}$).

→ Use Algorithm 4.2 or Algorithm 4.1 to compute $\lambda \overline{P+Q}, \lambda \tilde{P}$.

→ Compute the monodromy $\lambda \overline{P+Q} = \lambda_{1,P} \pi_q(\overline{P+Q}), \lambda \tilde{P} = \lambda_{0,P} \pi_q(\tilde{P})$.

→ Return $a_{\lambda, \ell}(P, Q) = \frac{\lambda_{1,P}}{\lambda_{0,P}}$

ALGORITHM 4.5. Ate pairing via cubical arithmetic

**Input:** $P \in \mathbb{G}_2, Q \in \mathbb{G}_1, \ell = \sum c_i q^i$

**Output:** The optimal Ate pairing (of level $m$) $a_{\sum c_i q^i}(P, Q)$

→ Take arbitrary rational affine cubical lifts of level $m \tilde{P}, \tilde{Q}, \overline{P+Q}$ of $P, Q, P+Q$ (along with a choice of $\tilde{0}$).

→ Use Algorithm 4.2 or Algorithm 4.1 to compute the $c_i \overline{P+Q}, c_i \tilde{P}$.

→ Apply Frobenius to compute the $\pi_q^i(c_i \overline{P+Q}), \pi_q^i(c_i \tilde{P})$.

→ Use cubical Three Way Additions to compute the $\sum \pi_q^i(c_i \overline{P+Q}), \sum \pi_q^i(c_i \tilde{P})$.

→ Compute the monodromy $\sum \pi_q^i(c_i \overline{P+Q}) = \lambda_{1,P} \tilde{Q}, \sum \pi_q^i(c_i \tilde{P}) = \lambda_{0,P} \tilde{0}$.

→ Return $a_{\sum c_i q^i}(P, Q) = \frac{\lambda_{1,P}}{\lambda_{0,P}}$

ALGORITHM 4.6. Optimal ate pairing via cubical arithmetic

easily correct our algorithm to do a cubical exponentiation rather than a projective point exponentiation. Our exponentiation $\ell P, \ell P+Q$, then gives “for free” our cubical points $\ell \tilde{P}, \ell \overline{P+Q}$, hence our pairings. Now in principle, there is no reason that the random affine arithmetic we use when computing $\ell P, \ell P+Q$ has any reason to be close to the cubical arithmetic; after all at each step we could multiply all our coordinates by some random constant since this does not change the projective point. But in practice, we use efficient algorithms (which do not involve doing random multiplications at each step). And the amazing thing is
that the ladder algorithms we already use, for the Theta, Montgomery, and short Weierstrass models, are already (almost) the correct cubical ones already, as we will see in Section 5. One explanation for this is the unicity of biextensions from Theorem 3.1, it appears that efficient formulas are sufficiently functorial in nature to satisfy the biextension arithmetic, or are close to.

In particular, in Section 5, we will look at the cubical representation on a Kummer line $E/ \pm 1$ resulting from affine lifts of sections $X, Z \in \Gamma(2(0_E))$. A biextension element will be given by $[\widetilde{P}, \widetilde{Q}, \tilde{0}, \widetilde{P+Q}]$ and the biextension exponentiation will be determined by $\ell \widetilde{P}$, $\ell \widetilde{P+Q}$ which are both described by two affine coordinates.

In Miller standard algorithm, one also compute the multiples $\ell P$ of $P$ (projectively, so with two projective coordinates $(X(\ell P) : Z(\ell P))$ if $P \in E/ \pm 1$ is a Kummer point), and store the Miller evaluations $f_{\ell,P}(Q)$ as a numerator and denominator separately, i.e., as an element of $\mathbb{P}^1$.

In fine, the affine lift representation is very similar: we store $X(\ell \widetilde{P}), Z(\ell \widetilde{P}), X(\ell \widetilde{P+Q}), Z(\ell \widetilde{P+Q})$ as affine coordinates, in a way such that $f_{2(0_E),\ell,P}$ is encoded by (see Porism 4.25)
$$f_{2(0_E),\ell,P}((Q) - (0)) = \frac{Z(\ell \widetilde{P+Q})Z(\tilde{0})}{Z(\ell \widetilde{P})Z(\widetilde{Q})} \left( \frac{Z(\widetilde{P})Z(\widetilde{Q})}{Z(\widetilde{P+Q})Z(\tilde{0})} \right)^{\ell} .$$
A word on how to interpret this last equality. The function $f_{2(0_E),\ell,P}$ has for divisor $2(\ell P) + 2(\ell - 1)(0_E) - 2\ell(P)$, so its evaluation on the cycle $(Q) - (0)$ gives a pole of order $2(\ell - 1)$ at 0. On the other hand $0_E = (1:0)$ so $Z(0_E) = 0$ is a zero of order two, and the right hand side also gives a pole of order $2(\ell - 1)$ at 0. The equality above makes sense by dividing both sides by $\pi_{0_E}^{2(\ell-1)}$ for any uniformizer $\pi_{0_E}$ at $0_E$; for instance divide both members by $Z^{\ell-1}$.

**4.6. Cubical functions.** Although we won't need this for pairings, we can generalize the construction of the cubical functions from Section 4.5.2 as follows, using the strategy of [Stao8, § 10.3].

Recall from Section 4.2.7 that if $Z = \sum n_i(Q_i)$ is a degree zero cycle such that $s(Z) = \sum n_i Q_i = 0$, then the choice of a cubical cycle $\widetilde{Z} = \sum n_i(\widetilde{Q}_i)$ is enough to competlely determine a function $f_{\widetilde{Z}}$ with divisor $\sum n_i D_{Q_i}$.

A way to specify $\widetilde{Z}$ is as follows: we consider a cycle of cycles: $Z = \sum n_i(Z_i)$, where $Z_i = \sum_j n_{ij}(P_{ij})$, and we will explain how to construct a cubical cycle $\widetilde{Z}$ above the cycle $Z = \sum n_i Z_i = \sum_{i,j} n_i n_{ij}(P_{ij})$, provided that $Z$ is of degree 0 with $s(Z) = 0$ (in fact we will need a stronger condition $S(Z) = 0$ to be introduced below).

We suppose that we have fixed once and for all cubical points $\widetilde{P}_{ij}, P_{ij} + \widetilde{P}_{i'j'}$. By Section 4.2.5, this completely determines cubical points $\sum n_{ij} \widetilde{P}_{ij}$, hence cubical points $\widetilde{Q}_i$ where $Q_i = s(Z_i)$, hence a cubical cycle $\widetilde{Z} = \sum n_i \widetilde{Q}_i$. Hence we have a well defined function $f_{\widetilde{Z}}$, which depends on the choices of $\widetilde{P}_{ij}, P_{ij} + \widetilde{P}_{i'j'}$ above. (The whole discussion could extends to when $s(Z) \in A[D]$ provided we have fixed $s(\widetilde{Z})$; as a notation we could use $\widetilde{Z} = \sum n_i \widetilde{T}_i \cdot Z_i$ to encode the cycle $Z = \sum n_i \widetilde{T}_i \cdot \widetilde{Q}_i$.)

We have $s(Z) = \sum n_i Q_i = \sum_{i,j} n_i n_{ij} P_{ij} \in A$. We let $S(Z) = \sum_{i,j} n_i n_{ij} P_{ij}$ as seen in the free abelian group generated by the $P_{ij}$. We have of course $S(Z) = 0 \Rightarrow s(Z) = 0$.

When $Z$ is of degree 0 with $S(Z) = 0$, we can compute the function associated to $\widetilde{Z}$ as follows. For a point $R$, take any cubical point $\tilde{R}, R + P_{ij}$. These choices completely determine
$R + \sum_j n_{ij} P_{ij}$, hence cubical points $R + \tilde{Q}_i$. We have:

$$f_{D_m, \tilde{Z}}(R) = \prod_i X_m(R + \sum_j n_{ij} P_{ij})^{n_i}.$$

As a reformulation, $f_{D_m, \tilde{Z}}(R)$ is given by the coordinate $X_m$ evaluated on the cubical cycle $\tilde{Z}_R$ encoded by $t_{R,*} \tilde{Z} = \sum_i n_i (R + \sum_j n_{i,j} P_{i,j})$.

Since $\tilde{Z}$ is a cycle of degree 0 with $S(\tilde{Z}) = 0$, by Section 4.2.5, the value $f_{D_m, \tilde{Z}}(R)$ only depends on $\tilde{P}_{ij}, P_{ij} + \tilde{P}_{i'j'}$, but not on the choices of $\tilde{R}, R + \tilde{P}_{ij}$.

More generally, let $Y = \sum_l m_l(R_l)$ be a cycle. Then we can consider the cycle of cycles $t_{Y_*} \tilde{Z} = \sum_{i,l} n_i m_l(R_l + Z_i)$, and apply the same strategy to obtain:

$$f_{D_m, \tilde{Z}}(Y) = \prod_{i,l} X_m(R_l + \sum_j n_{ij} P_{ij})^{n_i m_l}.$$

This only depends on the choice of $\tilde{P}_{ij}, P_{ij} + \tilde{P}_{i'j'}$, but not on the choices of $\tilde{R}_l, R_l + \tilde{P}_{ij}$. And by Lemma 4.7, if $\deg(Y) = 0$ then this does not depend on any choices.

**Example 4.29.** Let $X$ be a section of $\mathcal{L}$ with divisor $D$.

* The functions $g_{P,Q}$ with divisor $D_{P+Q} - D_P - D_Q$ from Section 4.5.3 corresponds to $\tilde{Z} = ((P) + (Q)) + ((0)) - ((P)) - ((Q))$.

* We can also build functions $g_{\ell P,Q}$ with divisors $D_{\ell P+Q} - D_{\ell P} - D_Q$ by considering $\tilde{Z} = (\ell(P) + (Q)) + ((0)) - (\ell(P)) - ((Q))$, we have seen in Section 4.5.3 that this is exactly $g_{i,P,Q}^{*1,\ell}$.

* The cycle of cycles $\tilde{Z} = (\ell(P)) + (\ell-1)((0)) - \ell((P))$ gives a function with divisor $D_{\ell P} - \ell D_P$.

If $P \in A[\ell D]$, then fixing a cubical point $\tilde{P}$ gives a function $g_{\ell P}$ with divisor $D_{\ell P}$, such that $g_{\ell P}(R) = X(\tilde{P} + \tilde{R})$ (by the definition of the action of $G(D)$ on cubical points), and we could say that $\tilde{Z} = (\ell(P)) + (\ell-1)((0)) - \ell((P)) - (\ell \tilde{P})$ gives a function with divisor $-\ell D_P$.

* If $P \in A[\ell]$, $\tilde{Z} = \ell((P)) - \ell((0))$ encodes a cubical cycle $\tilde{Z} = \ell \tilde{P} - \ell \tilde{Q}$, but while $s(\tilde{Z}) = 0$, $S(\tilde{Z}) = \ell P \neq 0$ in the free group generated by $P$, so we cannot simply construct the associated function as $X(R + \tilde{P})^\ell / X(\tilde{R})^\ell$; this would depend on the choices of $\tilde{R}$ and $R + \tilde{P}$.

We really need to encode the fact that $P$ is of $\ell$-torsion in $\tilde{Z}$ itself, i.e. to rewrite it as $\tilde{Z} = (\ell(P)) + (\ell-1)((0)) - \ell((P))$, as above.

**Example 4.30.** Sometimes, the function $f_{\tilde{Z}}$ does not even depend on the choices of $\tilde{P}_{ij}, P_{ij} + \tilde{P}_{i'j'}$, and we can use Section 4.2.5 to conveniently check if that is the case.

* Lets consider $\tilde{Z} = ((P) + (Q)) + ((0)) - ((P)) - ((Q))$ from Example 4.29 again. We have $(x_P + x_Q)^2 - x_P^2 - x_Q^2 = 2x_P x_Q$, so changing $\tilde{P}$ to $\lambda_P \tilde{P}$, $\tilde{Q}$ to $\lambda_Q \tilde{Q}$, $\tilde{P} + \tilde{Q}$ to $\lambda_P \lambda_Q \lambda'_{PQ} \tilde{P} + \tilde{Q}$, changes the resulting function $f_{\tilde{Z}}$ by a factor $\lambda'_{PQ}$. In fact we saw in Example 4.29 that we recover exactly the way to associate a biextension function $g_{P,Q}$ to our cubical points $\tilde{P}, \tilde{Q}, \tilde{P} + \tilde{Q}$.

* If $\tilde{Z} = ((P) + (Q) + (R)) + ((P)) + ((Q)) + ((R)) - ((P) + (Q)) - ((P) + (R)) - ((Q) + (R))$, then we have $(x_P + x_Q + x_R)^2 + x_P^2 + x_Q^2 + x_R^2 - (x_P + x_Q)^2 - (x_P + x_R)^2 - (x_Q + x_R)^2 = 0$, so $f_{\tilde{Z}}$ does not depend on our choice of
cubical points. In fact, this is precisely the function associated to cubical three way addition.

* If $\mathcal{Z} = ((P)+(Q)) + ((P)-(Q)) + ((0)) + ((0)) - ((Q)) - ((Q)) - ((P)) - ((P))$, then since $(x_P + x_Q)^2 + (x_P - x_Q)^2 - (-x_Q)^2 - (x_Q)^2 - (x_P)^2 - (x_P)^2$, then $f_{\mathcal{Z}}$ also does not depend on the choice of cubical points; this is the function associated to differential additions.

* If $[P_1, P_2, P_3, P_4; Q_1, Q_2, Q_3, Q_4]$ are in Riemann position, so that $Q_i = T - P_i$ with $2T = P_1 + P_2 + P_3 + P_4$, we can always find (possibly over a field extension) points $P'_i$ such that $2P'_i = P_i$ and $T = P'_1 + P'_2 + P'_3 + P'_4$, so that $Q_1 = -P'_1 + P'_2 + P'_3 + P'_4$ and so on.

Consider $\mathcal{Z} = (2(P'_1)) + (2(P'_2)) + (2(P'_3)) + (2(P'_4)) - ((P'_1) + (P'_2) + (P'_3) + (P'_4)) - ((P'_1) - (P'_2) + (P'_3) + (P'_4)) - ((P'_1) + (P'_2) - (P'_3) + (P'_4)) - ((P'_1) + (P'_2) + (P'_3) - (P'_4))$. Then $f_{\mathcal{Z}}$ also does not depend on the choice of cubical points, and actually gives the general Riemann relation on cubical points, because $(2x_{P'_1})^2 + (2x_{P'_2})^2 + (2x_{P'_3})^2 + (2x_{P'_4})^2 + (-x_{P'_1} + x_{P'_2} + x_{P'_3} + x_{P'_4})^2 - (x_{P'_1} - x_{P'_2} + x_{P'_3} + x_{P'_4})^2 - (x_{P'_1} + x_{P'_2} - x_{P'_3} + x_{P'_4})^2 - (x_{P'_1} + x_{P'_2} + x_{P'_3} - x_{P'_4})^2 = 0$.

The remarkable fact about the Riemann relations is that since the divisor of $f_{\mathcal{Z}}$ only involves $P_1, P_2, P_3, P_4, Q_1, Q_2, Q_3, Q_4$, we can compute it without involving the $P'_i$ (hence a field extension). We can reframe the previous invariance under the choice of cubical points as the computation $(x_{P_1})^2 + (x_{P_2})^2 + (x_{P_3})^2 + (x_{P_4})^2 - (x_T - x_{P_1})^2 - (x_T - x_{P_2})^2 - (x_T - x_{P_3})^2 - (x_T - x_{P_4})^2 = 0$ where $x_T := \frac{1}{2}(x_{P_1} + x_{P_2} + x_{P_3} + x_{P_4})$.

* Consider $\mathcal{Z} = (3(P)) - 9((P))$ (this example comes from [Sta08, Equation 10.13]). We have $(3x_P)^2 - 9x_P^2 = 0$, and indeed $X(3\tilde{P})/X(\tilde{P})^9$ does not depend on the choice of $\tilde{P}$. However, $s(\mathcal{Z}) = 3P - 9P = -6P \neq 0$, so $\mathcal{Z}$ is not associated to a function: we can check that $(x_R + 3x_P)^2 - 9(x_R + x_P)^2 = -8x_R^2 - 12x_P x_R$, hence the value of $X(\tilde{R} + 3\tilde{P})/X(\tilde{R} + \tilde{P})^9$ does depend on the choices of $\tilde{R}$ and $\tilde{R} + \tilde{P}$. In particular, replacing $\tilde{R}$ by $\lambda_R \tilde{R}$, and $\tilde{R} + \tilde{P}$ by $\lambda_R \lambda'_{RP} \tilde{R} + \tilde{P}$ changes this value by $\lambda_R^{-8} \lambda'_{RP}^{-6}$.

In summary, using a cycle of cycles $\mathcal{Z} = \sum n_i (\sum n_{i,j} P_{i,j})$ we can describe a cubical function $\tilde{R} \mapsto X(t_{R,*}\mathcal{Z}) = \prod_i X(R + \sum \tilde{n}_{i,j} P_{i,j})^{n_i}$; which in general depend not only on the choices of the $\tilde{P}_i, P_i + P_j$, but also on the choice of $\tilde{R}, R + P_i$.

When $\mathcal{Z}$ is of degree 0 and $s(\mathcal{Z}) = 0$, $\mathcal{Z}$ encodes a genuine function which descends on the abelian variety. But to compute it in practice as the evaluation of some coordinate $X$ on the cycle $t_{R,*}\mathcal{Z}$ we need the stronger condition that $S(\mathcal{Z}) = 0$. In this case, the function only depends on the choices of $\tilde{P}_i, P_i + P_j$. This makes it very practical to build functions with prescribed divisors, such as the ones used in Theorem 4.28.

Finally, for certain well chosen cycles of cycles (e.g., coming from the algebraic Riemann relations), the function is canonical and does not depend on the choice of any cubical points. These canonical functions can then be used to compute the cubical arithmetic.

**Example 4.31.** Let $\phi : E_1 \to E_2$ be an isogeny of odd degree $\ell$ with kernel $K = \langle P \rangle$ between Montgomery Kummer lines. We assume furthermore that if $T = (0:1)$ on $E_1$, $T' = (0:1)$ on $E_2$, we have $\phi(T) = T'$. The coordinate $x'$ on $E_2$ has for divisor $2(T') - 2(0_{E_2})$ hence $\phi^*x'$ has for divisor $\sum_{i=0}^{\ell-1} (2(T + iP) - 2(iP))$. Since $\mathcal{Z}$ has for zero divisor $2(0_E)$, for a $R \in E_1$, making arbitrary choices for $\tilde{R}, R + P$, we consider the following product of cubical functions: $\Phi(R) = \prod_{i=0}^{\ell-1} Z(R + \tilde{iP} + T)Z(R + \tilde{iP})^{-1}$. If we take $\tilde{T}$ such that the induced theta group
action is $\tilde{T} \cdot (X, Z) = (Z, X)$, we obtain $\Phi(R) = \prod_{i=0}^{\ell-1} \frac{X(R+iP)}{Z(R+iP)} = \prod_{i=0}^{\ell-1} x(R+iP)$, which indeed has the correct divisor and evidently does not depend on any choice of cubical points.

### 4.7. Cubical arithmetic and pairings on Kummer varieties.

#### 4.7.1. Biextension additions on Kummer varieties.
Let $(A, \mathcal{L})$ be a principally polarised abelian variety, if $\mathcal{L}$ is indecomposable then $\mathcal{L}^2$ gives an embedding of the Kummer variety $A/\pm 1$.

Let $(X_1, \dots, X_m) \in \Gamma(\mathcal{L})$ be the global sections of $\mathcal{L}$ (we will call these level 2 coordinates). We then have by Section 4.5 the affine lift representation $\tilde{P} = (X_1(\tilde{P}), \dots, X_m(\tilde{P}))$. The projective coordinates $(X_1(P) : \dots : X_m(P))$ only allows to recover $\pm P$, so in this case our affine lift representation for $\tilde{P}$ only recovers $\pm \tilde{P}$.

However, when using the affine lift representation for the cubical points in the cubical biextension representation $g_{P,Q} = [\tilde{P}, \tilde{Q}; \tilde{0}, P+Q]$, then by [LR16] the points $P, Q$ are determined up to the same sign. The reason is that, if $Q$ is not of 2-torsion, the map $A \to A/\pm 1 \times A/\pm 1, P \mapsto (\pm P, \pm (P+Q))$ is an embedding (and if both $P, Q$ are of 2-torsion we can use the action of the theta group $G(\mathcal{L}^2)$ instead). Since pairings are bilinear, this representation of $g_{P,Q}$ is enough to recover the pairings $e(P, Q)$ exactly.

We just need to explain how to do a cubical biextension exponentiation using affine coordinates of level 2. The cubical ladder from Algorithm 4.2 works as is; we just need affine doublings and differential additions that lift the standard doublings and differential additions on the Kummer variety to the cubical arithmetic. However, for the cubical double and add algorithm from Algorithm 4.1, the algorithm requires a cubical biextension addition, which requires to lift an abelian variety standard addition.

We cannot do a standard addition on a Kummer variety. However, in the context of a cubical biextension addition, we are given representations $g_{P_1,Q} = [\tilde{P}_1, \tilde{Q}; \tilde{0}, P_1+Q]$ and $g_{P_2,Q} = [\tilde{P}_2, \tilde{Q}; \tilde{0}, P_2+Q]$ and we want to compute a representation $g_{P_1,Q} *_1 g_{P_2,Q} = [P_1+\tilde{P}_2, \tilde{Q}; \tilde{0}, P_1+\tilde{P}_2+Q]$. We note that our affine lift representation, when interpreted as projective coordinates, give us the coordinate of $\pm P_1, \pm P_2, \pm Q, \pm(P_1+Q), \pm(P_2+Q)$ on the Kummer variety. This data is enough to compute a compatible addition $\pm(P_1+P_2) = \text{CompatibleAdd}(\pm P_1, \pm P_2; \pm Q, \pm(P_1+Q), \pm(P_2+Q))$ as explained in [LR16]. Take any affine lift $P_1+\tilde{P}_2$ of $\pm(P_1+P_2)$, and then proceed to compute $P_1+\tilde{P}_2+Q$ via a three way addition like in the usual case. This gives Algorithm 4.7.

We obtain the following algorithm to compute the pairings associated to $\mathcal{L}^2$ on an abelian variety $A$. Let $P, Q \in A$, compute $P+Q \in A$, and then compute the projective coordinates $X_i(P), X_i(Q), X_i(P+Q)$ to get the points $\pm P, \pm Q, \pm(P+Q)$ on $A/\pm 1$. Take arbitrary lifts of these projective coordinates to get a representation of $g_{P,Q} = [\tilde{P}, \tilde{Q}; \tilde{0}, \tilde{P}+Q]$.

The pairings then requires to compute biextension exponentiations which can be done using Algorithms 4.2 and 4.7, and eventually the action of the theta group $G(\mathcal{L}^2)$ (to compute pairings with $\ell$ even) or the action of $\pi_q$ (for the optimal Ate and optimal Ate pairings) which can be expressed naturally as in Section 4.5 on the level 2 affine coordinates $X_i$.

#### 4.7.2. Pairings on Kummer varieties.
The computation of $\pm(P+Q)$ (via its coordinates $X_i(\pm(P+Q))$) requires to start with $P, Q \in A$. If we want to compute pairings which genuinely lie on the Kummer variety, we then have only $\pm P, \pm Q$. The best we can compute from these points is the degree two étale subscheme $\pm(P \pm Q)$ of $A/\pm 1$. This subscheme is isomorphic to $\text{Spec } R$, with $R = k[X]/\mathfrak{P}(X)$, $\mathfrak{P}$ a polynomial of degree 2. Typically, if $X_1$ is a separating coordinate, we can take $\mathfrak{P}(X) = (X - X_1(P+Q))(X - X_1(P-Q))$ and express the isomorphism between $\text{Spec } R$ and $\pm(P \pm Q)$ by giving linear relations between