Smooth E8 Manifold

Blog

Miller’s Algorithm and Pairing
Recently I’m implementing some optimizations related to pairing calculations in elliptic curve cryptography. This note summarises some of my learning so far, and I hope it would be helpful for someone coming from a pure maths background who wants to learn about implementation and optimization details.

Elliptic Curve Pairing For Mathematicians

A pairing in cryptography is a bilinear map with certain computational properties that are very useful for cryptography applications. There are many applications for pairing-based cryptography and I will not go over them here. The Weil pairing was the first proposed pairing map, which is really the Poincaré duality for Étale cohomology. In practice, cryptographers use other related variants (e.g. Tate pairing coming from Poitou-Tate duality) for performance reasons. For someone whose background was not in number theory, I found Silverman’s survey to be a clear conceptual explanation of where the various pairings arise from.

For an elliptic curve (a smooth, projective algebraic curve of genus 1 with a marked point ${\mathcal{O}}$ ), its rational points are in bijection with the degree zero part of its Picard group. One proof of this fact is based on a dimensionality argument using Riemann-Roch. Concretely, this map sends a point ${\mathcal{P}}$ to the line bundle represented by the divisor ${(\mathcal{P}) - (\mathcal{O})}$ . Tensor product of line bundles in the Picard group induces a multiplication map on the rational points, which recovers the classical group law.

Miller’s Algorithm

In practice, computing pairings on elliptic curves in some presentation can be challenging although it’s conceptually clear (to algebraic geometers) that they define a bilinear map. The original paper of Miller considers the problem of computing a rational function on an algebraic curve that corresponds to a given divisor (in the sense that the given divisor is equivalent to some effective divisor given that function). For an elliptic curve, this basically boils down to the identity

$\displaystyle (div(h_{\mathcal{P}, \mathcal{Q}})) = (\mathcal{P}) + (\mathcal{Q}) - (\mathcal{P} + \mathcal{Q}) - (\mathcal{O}), \ \ \ \ \ (1)$

where ${h_{\mathcal{P}, \mathcal{Q}}}$ is the function of the line passing through ${\mathcal{P}}$ and ${\mathcal{Q}}$ , where ${h_{\mathcal{P}, \mathcal{Q}}}$ is a rational function representing the ratio of two lines that we will define later. Equation 1 follows straightforwardly from the following two identities corresponding to divisors that represent the line passing through ${\mathcal{P}}$ and ${\mathcal{Q}}$ and the vertical line at ${x}$ -coordinate ${\mathcal{P}+\mathcal{Q}}$ .

$\displaystyle (y - \lambda x - v) = (\mathcal{P}) + (\mathcal{Q}) + (-\mathcal{P} - \mathcal{Q}) - 3(\mathcal{O}), \ \ \ \ \ (2)$

$\displaystyle (x - x_{\mathcal{P}+\mathcal{Q}}) = (\mathcal{P} + \mathcal{Q}) - (\mathcal{P} + \mathcal{Q}) - 2(\mathcal{O}). \ \ \ \ \ (3)$

We then set ${h_{\mathcal{P}, \mathcal{Q}} = \frac{y - \lambda x - v}{x - x_{\mathcal{P}+\mathcal{Q}}}}$ to recover the desired identity. Miller’s algorithm (as described below) then uses (1) at each step to compute the rational function whose divisor corresponds to ${N(\mathcal{P}) - (N(\mathcal{P})) - (N-1)(\mathcal{O})}$ for an ${N}$ -torsion point ${\mathcal{P}}$ , where the proof essentially follows from a telescoping sum argument.
```
Set  and  

Loop  down to  

  Set  

  Set  

  If  

    Set  

    Set  

  End If 

End  Loop 

Return the value 
```
(This section follows the presentation in Silverman’s book on the arithmetic of elliptic curves.)

Optimization

There are many techniques to speed up pairing calculations; I’ll probably address them in a later post. The notes gives a detailed discussion on the optimization details of pairing calculations. One particular optimization related to computing the Miller loop is that one can drop the denominator of the line function (so-called “denomination elimination” technique).
10th Oct 2025
Gröbner bases and geometry
Algebra is the offer made by the devil to the mathematician. The devil says: “I will give you this powerful machine, it will answer any question you like. All you need to do is give me your soul: give up geometry and you will have this marvelous machine. — Michael Atiyah

Back in the day when dinosaurs still roamed Palo Alto and I was a clueless Stanford junior undergrad, I tried and failed many times to understand Gröbner bases. Now I have to implement Gröbner bases for my research, after a Saturday’s suffering, I finally seem to understand what’s going on with Gröbner bases from the wonderful paper [1] What can be computed in algebraic geometry?. This note summarises my learning so far. In retrospect, I hope someone taught me this when I took my first scheme-based algebraic geometry class as an example of the subtlety of algebraic structures compatible with algebraic varieties.

Gröbner Bases

First recall Buchberger’s algorithm which finds a basis for an ideal ${I}$ of a polynomial ring ${R}$ proceeds as follows (pseudo-code generated by Claude based on the Wikipedia page).

Input A set of polynomials ${F}$ that generates ${I}$

Output A Gröbner basis ${G}$ for ${I}$
1. ${G := F}$
2. For every ${f_i, f_j}$ in ${G}$ , denote by ${g_i}$ the leading term of ${f_i}$ with respect to the given monomial ordering, and by ${a_{ij}}$ the least common multiple of ${g_i}$ and ${g_j}$ .
3. Choose two polynomials in ${G}$ and let ${S_{ij} = \frac{a_{ij}}{g_i} f_i - \frac{a_{ij}}{g_j} f_j}$ (Note that the leading terms here will cancel by construction).
4. Reduce ${S_{ij}}$ with the multivariate division algorithm relative to the set ${G}$ until the result is not further reducible. If the result is non-zero, add it to ${G}$ .
5. Repeat steps 2–4 until all possible pairs are considered, including those involving the new polynomials added in step 4.
6. Output ${G}$ .
When I first learnt about this, it seemed to me extremely unclear what exactly is going on. Why do we choose a monomial ordering? How does the choice of a different monomial ordering affect the runtime? The geometric insight in [1] is to relate the monomial ordering to a 1-parameter family of automorphism of the projective space wherein the variety defined by the set of polynomials ${F}$ embeds.

In particular, let ${X}$ be the algebraic variety defined by ${F}$ (take homogenization) in some projective scheme ${\mathbb{P}^n}$ , consider a one-parameter subgroup ${\lambda(t) \subset GL(n + 1)}$ of the diagonal form

$\displaystyle \lambda(t) = \begin{bmatrix} t^{w_0} & & & \\ & t^{w_1} & & \\ & & \ddots & \\ & & & t^{w_n} \end{bmatrix},$ where each ${\lambda(t)}$ induces an automorphism of ${\mathbb{P}^n}$ where we identify the image of ${X}$ as ${X_t}$ . Let ${x^A = x_0^{a_0}\ldots x_n^{a_n}}$ be a monomial in the homogeneous coordinate ring of ${\mathbb{P}^n}$ . Then the automorphism ${\lambda(t)}$ maps a homogenous polynomial ${f = ax^A + bx^B + \ldots}$ to ${\lambda f = at^{W\cdot A}x^A + bt^{W\cdot B}x^B + \ldots}$ .

From here, one may take projective limits of ${\lambda f}$ and ${X_t}$ in the projective spaces and ponder what happens at ${t = 0}$ . The upshot is that with a particular choice of the one-parameter automorphism groups, we can recover exactly the monomial ordering (exercise: recover the lexicographic and reverse lexicographic ordering this way; the reverse lexicographic order described in [1] is actually the graded lexicographic order, but they coincide here since we consider homogeneous coordinates) as the projective limit of ${\lambda f_t}$ for ${t}$ away from ${0}$ .

Back to the question about what happens to ${\varprojlim X_t}$ as ${t}$ approaches ${0}$ , the “right” perspective is to define a ${\mathbb{P}^n[t]}$ -scheme ${X'}$ whose fiber at ${t}$ recovers ${X_t}$ . An obvious attempt is to define ${X'}$ to be generated by each ${g_t}$ as the quotient of ${f}$ divided by the largest power of ${t}$ in its monomials, which would recover ${X_t}$ at fibers away from ${0}$ . However, at ${t = 0}$ , the situation is not nice as the projection from ${X'}$ is not necessarily flat (or equivalently the syzygies upstairs do not generate the ones downstairs). To make it flat, we lift syzygies upstairs, which amounts to adding “ ${t}$ -torsion” points to the coordinate rings, which recovers exactly the “multivariate division” part of Buchberger’s algorithm! Therefore the Gröbner bases in some sense define a flat family of varieties whose fiber at general position recovers the original variety ${X}$ .

Connections to Regularity

It turns out Gröbner bases relate to Hilbert functions and its computational complexity relates to Castelnuovo-Mumford regularity (also can be used to construct Hilbert schemes). I strongly recommend working through the example in [1] to gain intuition. One particular nice thing is that reducing by lexicographic order or reversed lexicographic order is related to projection of the orignal variety to some subspaces ([1] discusses really cool connections to flag varieties in birational geoemtry). The upshot is that lexicographic order reduction corresponds to the projection ${\mathbb{P}^n \rightarrow \mathbb{P}^{n-1}}$ where ${\mathbb{P}^n}$ is viewed as the Thom space of the tautological bundle over ${\mathbb{P}^{n-1}}$ and reverse lexicographic order reduction corresponds to projection from the point at infinity. This intuitively explains why in practice reverse lexicographic order reduction works better, as the relevant projection maps are simpler – which is pretty cool as the hidden geometry is not obvious at all if one only thinks about the ordering.
16th Aug 2025
Starting a blog

Hey there! I just started a blog. I’ll probably post about things that I am reading or find interesting, which may include computer science, algebraic geometry, probability, and some topology.

4th Mar 2021