I'm studying Weil pairing and its applications in cryptography. I already know that it can be defined like this:

$$w(P, Q) = (-1)^n\frac{f_P(Q)}{f_Q(P)}\frac{f_Q}{f_P}(\mathcal{O})$$

where

$\textrm{div}(f_P) = n(P) - n(\mathcal{O})$ and $\textrm{div}(f_Q) = n(Q) - n(\mathcal{O})$.

This is not suitable for computation, so we shift the numerator by $R$ and the denominator by $S$ and we obtain:

$$w(P, Q) = (-1)^n\frac{g_P(Q+S)}{g_Q(P+R)}\frac{g_Q(R)}{g_P(S)}$$

where

$\textrm{div}(g_P) = n(P+R) - n(\mathcal{R})$ and $\textrm{div}(g_Q) = n(Q+S) - n(\mathcal{S})$.

Enter Miller's algorithm. In order to calculate $g_P(A)$ we define $h_k$ for $k = 0,\ldots,n$ as:

$$\textrm{div}(h_k) = k(P+R) - k(R) - (kP) + \mathcal{O}$$

Now, $h_n = g_P$ and we can calculate $h_{k+l}(A)$ from $h_k(A)$ and $h_l(A)$. So we construct a "double-and-add" algorithm similar to fast exponentiation.

Although $g_P(A)$ is never zero or infinity (for $A = Q+S$ or $A = S$), it can happen that during the execution of "double-and-add" algorithm we can encounter some $h_k(A)$ equal to zero or infinity. The solution is to randomly select new $Q$ and $S$ and start over.

How do I prove that there exist such $Q$ and $S$ that I will be able to calculate the Weil pairing of $P$ and $Q$?

If possible, I'd like to see some simple argument that does not refer to algebraic geometry, as I don't know anything about it - I come from cryptography.

JoeSilverman. I'm an idiot. $\endgroup$ – paul garrett Jun 27 '11 at 19:31