2

I am trying to find a concrete example of the Weil Pairing. What I have done until now is that I took $E=(x-1)(x-2)(x-3)$ over $F_5$. I took $E[2]=\{\infty,(1,0),(2,0),(3,0)\}$. I know that there exist a rational function f such that \begin{equation*} div(f)=2[T]-2[\infty] \end{equation*} How can I find this function f? How can I find the points of order 4? How should I continue?

otus
  • 32,132
  • 5
  • 70
  • 165
user28082
  • 173
  • 7
  • Have a look here. And as for finding the points of order $4$, are you allowed to use a computer? I yes, Sage or Pari/GP will do. Otherwise, you can find all points with pen and paper, and identify those of order $4$. – fkraiem Oct 14 '15 at 12:56
  • thank I you! I use matlab. Is there an esay way to find the points of order 4? Is there a known algorithm to identify points of a certain order? – user28082 Oct 14 '15 at 14:18
  • I do not know Matlab. In Pari, you can obtain generators of the cyclic components of the group, from which it is trivial to obtain the points of any order. – fkraiem Oct 14 '15 at 14:25
  • I did not know Pari. It looks interesting for such kind of computations! Could you explain me a litte bit more how to do this with Pari? – user28082 Oct 14 '15 at 14:30
  • The comments are not meant to be used for discussions, so please send an e-mail, I will answer tomorrow as it is late here (but FYI, you use the Pari function ellgroup()). – fkraiem Oct 14 '15 at 14:32

1 Answers1

2

The automatic way to find f is by using the Miller algorithm.

But you can also see this directly here: Since the line y=0 is not tangent to E , y is a uniformizing function. You can write $(x-1) = y^2*((x-2)(x-3))^{-1}$, where $(x-2)*(x-3)$ has neither a zero nor a pole at (1, 0). This says exactely that (1,0) is a double zero of the function x-1. Since it has a double zero it must also have a double pole at $\infty$. This gives you \begin{equation*} div((x-1))=2[(1,0)]-2[\infty] \end{equation*}

In a similar way you can show this for the points (2,0) and (3,0)

Now you have all 2-torsion points, lets find the other points:
x=0 gives $y^2 = -1$, which solves to y=2 and y=3
x=4 gives $y^2 = 1$, which solves to y=1 and y=4
Since the group has 8 elements, at least two of those points must have order 4. That all 4 points have order 4 can be shown by a direct calculation(2 squarings are sufficient). One can also see this by a direct argument:
If the group would be cyclic, it would have 4 elements of order 8. This would let no place for an element of order 4. Therefore the group cannot be cyclic and all 4 elements, which are not 2-torsion elements, must have order 4.

  • wow! thank you! this really helped me! One additional question. You said:Since the group has 8 elements, at least two of those points must have order 4. How do you know this? – user28082 Oct 23 '15 at 16:03
  • The group has 8 elements by simply listing them. The 2-torsion consists of four points. Any other point generates a cyclic subgroup of E, and therefore its order must divide the group order, The order o of this cyclic group must therefore be 4 or 8. This group must have a subgroup of order 4. That you have two elements of order 4 stems from the fact that all points, which are not on the x-line occur in conjugated pairs. –  Oct 23 '15 at 16:21