Wrong Miller's Weil Pairing implementation?

Question

I tried to implement the Miller's Weil Pairing algorithm in python using the book "An introduction to mathematical cryptography" by Hoffstein, Pipher and Silverman.

I tried my code with the example given in the book and I get the correct response.

I tried with another example but I have problems with it.
It is stated in the book that we must choose a random point S $\notin$ {0, P, -Q, P-Q}. I took the following elliptic curve $E : Y² = X³ + 3X + 8$ over the field $\mathbb{F}_{13}$.

$E(\mathbb{F}_{13}) = \{0, (1,5), (1,8),(2,3),(2,10),(9,6),(9,7),(12,2),(12,11)\}$

I tried to compute $e(P,Q)$ with $P = (1,5)$ and $Q = (12,2)$. As $-Q = (12,11)$ and $P-Q = (9,6)$, I tried with all the other points but I always have an error at some points in the computations because I end up with zeros at both numerator and denominator in this function.

There is probably something that I didn't understand or something wrong with my implementation. Could someone explain to me what is the problem ?
Here is my code with the first example that works and the second that causes the problem : http://tpcg.io/GZNfns

Answer 1

The reason your implementation fails is most likely because the result of the Weil pairing is 1 in this case, which is the most degenerate case and the one most likely to encounter division by zero errors.

Your elliptic curve $y^2 = x^3 + 3x + 8$ over $\mathbb{F}_{13}$ is cyclic. In this case, $P$ is a generator of $E$ (as is $Q$), and $P$ and $Q$ satisfy the relationship $Q = 4P$, so the Weil pairing is trivial: $$ e(P,Q) = e(P,4P) = e(P,P)^4 = 1^4 = 1 $$ (The second-to-last equality above follows from the antisymmetry property of the Weil pairing.)

If you want a non-trivial Weil pairing, you need a non-cyclic elliptic curve group, such as the curve from the first example. In cryptography one usually uses an elliptic curve defined over an extension of a prime field instead of a curve defined over a prime field, in order to guarantee that the group is non-cyclic.