It is all pairings... this is a rather complex matter. I recommend reading Ben Lynn's PhD dissertation; it is about as nice an introductory text on pairings as you can get.
The definition is rather mind-twisting:
You first define divisors, which are rather formal objects. It is the free group of the curve points: for each curve point $P$, you define a divisor $(P)$, and then you add divisors together, so the complete form of a divisor is a linear combination: $\sum_{P\in E} a_P (P)$. This is a formal sum: all the linear combinations are deemed distinct from each other. In particular, $(P+Q)$ (the divisor associated with the point $P+Q$) is not the same as $(P)+(Q)$ (which is the sum of two elementary divisor, and is thus a divisor in its own right, but not associated with a curve point). Each $a_P$ is an integer (possibly negative).
Then you consider rational functions over the curve (these are functions $f = R_1(x,y)/R_2(x,y)$ where $R_1$ and $R_2$ are polynomials, and $(x,y)$ are the coordinates of curve points).
Then you establish a kind of bijection between divisors and rational functions. The function $f$ has zeros (roots of polynomial $R_1$) and poles (roots of polynomial $R_2$): you map $f$ to a divisor $\sum_{P\in E} a_P (P)$ such that:
- if $P$ is a zero of multiplicity $n$ then $a_P = n$;
- if $P$ is a pole of multiplicity $n'$ then $a_P = -n'$;
- otherwise $a_P = 0$.
It so happens that to a given divisor corresponds a unique rational function $f$, up to a multiplicative constant. This is not completely surprising: we know that a polynomial can be rebuilt (up to a multiplicative constant) from knowledge of its roots: if polynomial $T$ has root $t_1$ with multiplicity $2$ and root $t_2$ with multiplicity $3$, then $T = \alpha (X-t_1)^2(X-t_2)^3$ for some constant $\alpha$. Here, this is extended to rational functions, which contain two polynomials, hence the zeros and the poles (our $f$ functions are over two variables $x$ and $y$ instead of one, but the same principle is at work here). We denote the divisor corresponding to function $f$ by $\operatorname{div}(f)$.
Then the really confusing part: for some reason, we begin to apply rational functions to divisors. It took me some time to understand this step. We define a new operation which takes a rational function $f$ and a divisor $D$, and computes $f(D)$. Then magic occurs: for two functions $f$ and $g$, we have $f(\operatorname{div}(g)) = g(\operatorname{div}(f))$ (the "Weil reciprocity").
Then we define the Weil pairing as a quotient of two such applications of functions on divisors. The quotient makes the multiplicative constants disappear, and the result is well-defined.
Then you want to compute the pairing. Mathematically, you would need to build two huge rational functions (the polynomials would have $2^{160}$ or so coefficients, so that's not feasible) and then apply these functions to some divisors (which are equally humongous). However, since we are just interested in the final application result, we can remove a lot of needless complexity, and that's Miller's algorithm.
All of this suppose that you start with a finite field $\mathbb{F}_q$ for some $q$ (a prime or a prime power), then do all computations in some extension field $\mathbb{F}_{q^k}$ for some $k$ called the embedding degree. Theory shows that if your points of interest have order $r$ (a prime number)(points of order $r$ are called $r$-torsion points), then the pairing remains trivial (you get $1$ at the end), until $k$ is "large enough": precisely, the $k$ value at which things get interesting is the smallest $k \geq 2$ such that $r$ divides $q^k-1$ (that the Balasubramanian-Koblitz theorem).
For normal curves, the embedding degree $k$ is ludicrously high (the same order of magnitude as $q$), so you would have to do computations with numbers too large to fit in your computer, or, for that matter, in the Universe taken as a whole. However, if the curve is so that $k$ is small, then the pairing can be computed, and the MOV attack reduces the problem of discrete logarithm on the curve to the problem of discrete logarithm in $\mathbb{F}_{q^k}$, which can be substantially simpler.
In particular, when $q$ is prime and equal to $3$ modulo $4$ and the curve is $Y^2 = X^3+aX$, then $k = 2$. If $q$ is a 256-bit integer, then the MOV attack turns discrete logarithm over a 256-bit curve (infeasible) into discrete logarithm in a 512-bit field (hard but feasible).
Implementing pairings is a deep exploration into non-trivial mathematics. It is enlightening, but daunting. For practical purposes it may be simpler to rely on some existing code, e.g. Ben Lynn's PBC library).
(I am writing all of this from memory, there could be some mistakes. Feel free to fix them.)
