Eventually, then, we’re in a position to compute Tate pairings in SAGE. The necessary ingredients are an elliptic net class (the more general one or a faster version for pairings only), an eds class (this one based on Stange’s algorithm is recommended and used in the examples below; the old one should also work), and supporting procedures tate.
Load these in the usual fashion:
sage: attach "tate.sage" sage: attach "ellnet1d.sage" sage: attach "ellnet2d.sage"
We now need to introduce a curve and some points. Stange gives a simple example of y^2+y=x^3+x^2-2x over the field with 5 elements corresponding to points P=(0,0) and Q=(1,0). We enter the field, curve and points and set up an elliptic net:
sage: K=GF(5)
sage: E=EllipticCurve(K,[0,1,1,-2,0])
sage: E
Elliptic Curve defined by y^2 + y = x^3 + x^2 + 3*x over Finite Field of size 5
sage: P=E([0,0])
sage: Q=E([1,0])
sage: X=netFromPoints(P,Q)
sage: X
Elliptic net with (1,0) block:
1 1 1
4 4 0 1 1 2 1 3
The block centred at 1 is displayed; this has been generated from the initial data, and suffices to compute any term of the form (x,0) or (x,1). If such a term is known, it is simply retrieved from the hash table; otherwise, the algorithm is employed. Requests for unreachable points give a ValueError:
sage: X.has_element((5,0))
True
sage: X[(5,0)]
3
sage: X.has_element((100,1))
False
sage: time X[(100,1)]
Computing terms
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01
1
sage: X.has_element((100,1))
True
sage: time X[(100,1)]
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00
1
sage: X[(100,2)]
---------------------------------------------------------------------------
<type 'exceptions.ValueError'> Traceback (most recent call last)
/home/s0677951/SAGE/eds/<ipython console> in <module>()
/home/s0677951/SAGE/eds/ellnet2d.py in __getitem__(self, A)
41 # Term not entered and cannot be computed; give an error.
42 raise ValueError, \
---> 43 "Term unavailable, cannot compute unless of form (x,0) or (x,1)"
44
45 def has_element(self, A):
<type 'exceptions.ValueError'>: Term unavailable, cannot compute unless of form (x,0) or (x,1)
You can also test for and print entire (small)blocks; this illustrates the route taken during computation of elements, for instance in computing the 18th term, the blocks with centres 1, 2, 4, 9 are constructed, then the small block centred on 18:
sage: X.has_block((9,0))
False
sage: X[(18,0)]
Computing terms
0
sage: X.has_block((9,0))
True
sage: X.print_block(9,0)
1 1 3
4 3 2 0 3 2 1 2
sage: X.has_block((18,0))
False
sage: X.has_small_block((18,0))
True
sage: X.print_small_block(18,0)
2 4 3
3 4 4 0 1 1 2
To compute the pairing of P and Q, use TatePairing(m,P,Q), where m is the order of P (determining this left as an exercise!):
sage: TatePairing(9,P,Q) Computing terms 3
Finally, a call to TatePairing with P=Q will construct an eds rather than an ellnet. We can verify an example of Stange’s (see slides from ECC):
sage: K=GF(73) sage: E=EllipticCurve(K,[0,1,1,-2,0]) sage: P=E([0,0]) sage: TatePairing(9,P,P) Computing terms 24
