## Pairings or bilinear maps

tl;dr: Pairings, or bilinear maps, are a very powerful mathematical tool for cryptography. Pairings gave us our most succinct zero-knowledge proofs[^GGPR12e]$^,$[^PGHR13e]$^,$[^Grot16], our most efficient threshold signatures[^BLS01], our first usable identity-based encryption (IBE)[^BF01] scheme, and many other efficient cryptosystems[^KZG10]. ...

## Lagrange interpolation

Recall from our basics discussion that a polynomial $\phi$ of degree $d$ is a vector of $d+1$ coefficients: \begin{align} \phi &= [\phi_0, \phi_1, \phi_2, \dots, \phi_d] \end{align} How to compute a polynomial’s coefficients from a bunch of its evaluations Given $n$ pairs $(x_i, y_i)_{i\in[n]}$, one can compute or interpolate a degree...

Multiplicative inverses modulo $m$ The multiplicative group of integers modulo $m$ is defined as: \begin{align} \Z_m^* = \{a\ |\ \gcd(a,m) = 1\} \end{align} But why? This is because Euler’s theorem says that: \begin{align} \gcd(a,m) = 1\Rightarrow a^{\phi(m)} = 1 \end{align} This in turn, implies that every element in $\Z_m^*$ has an invers...