trace of Frobenius

Question

how can I calculate trace of Frobenius for a single point on an elliptic curve $E(F_{q^{12}})$? I've tried to sum up 12 points that were different powers Frobenius maps but none of the points don't map to $F_q$ as it should be (correct me if I wrong). this is a snapshot below from which I got a formula to calculate the trace of frobenius. Formula to compute the trace of Frobenius from "Assymetric Pairings" by Alfred Menezes

Answer 1

I took a glance to the paper / rather to the slides in ECC2009, Menzes, pure curiosity, and decided to start an answer. The question is not fully clear to me now, i will give an answer by example that explicitly computes the trace of Frobenius for a point for some explicit curve. Sage will be used.

---

First, we have to set up a detailed framework instead of the slide pages 10, 11, 12 in loc. cit., best by example.

Let us find first a pair $n,p$, $n=f(z)$, $p=g(z)$ for the polynomials specified in the slides. Sage code for the search among some small numbers:

sage: def f(z): return 36*z^4 + 36*z^3 + 18*z^2 + 6*z + 1
sage: def g(z): return 36*z^4 + 36*z^3 + 24*z^2 + 6*z + 1

sage: for z in [-100..100]:
....:     if f(z) > 0 and g(z) > 0 and f(z).is_prime() and g(z).is_prime():
....:         print "z = %3s n = %10s p = %10s" % ( z, f(z), g(z) )
....:         
....: 
z = -55 n =  323487121 p =  323505271
z = -52 n =  258204649 p =  258220873
z = -41 n =   99276253 p =   99286339
z = -15 n =    1704961 p =    1706311
z =  -7 n =      74929 p =      75223
z =  -3 n =       2089 p =       2143
z =  -2 n =        349 p =        373
z =  -1 n =         13 p =         19
z =   1 n =         97 p =        103
z =   5 n =      27481 p =      27631
z =   6 n =      55117 p =      55333
z =   7 n =      99709 p =     100003
z =  20 n =    6055321 p =    6057721
z =  78 n = 1349735869 p = 1349772373
z =  82 n = 1647609109 p = 1647649453

For our purposes the case $n=97$, $p=103$ should be fine. (It is not the simplest one, $13,19$. Just a choice.)

Then indeed, the minimal $k$ such that $n$ divides $p^k-1$ is $12$,

sage: factor(p^12-1)
2^5 * 3^2 * 5 * 7 * 13 * 17 * 19 * 37 * 79 * 97 * 1061 * 3571 * 31357

sage: for k in [1..12]:
....:     if (p^k - 1) % n == 0:
....:         print k
....:         
12

We need now an explicit $b$, such that the curve $E=E_b$ defined over $F=\Bbb F_p$, $$E=E_b\ :\ Y^2 = X^3+b $$ has order (of the group of $F$-rational points$) $n=|E(F)|$. Let us search for the $b$.

sage: for b in F:
....:     try:
....:         E = EllipticCurve(F, [0,b])
....:     except:
....:         continue
....:     if n == E.order():
....:         print b
....:         
5
11
12
21
40
45
47
51
53
65
67
70
71
86
88
96
99
sage: 

My choice is then the 5. So we work with $$ E\ :\ Y^2 = X^3 + 5\text{ over }F =\Bbb F_{103}\ ,\ |E(F)|=n=97\ . $$ The paper claims that all points in $E[n](\bar F)$ live over $F':=\Bbb F_p^{12}$, let us check:

sage: set( [ pol.degree() for pol, mul in E.division_polynomial(97).factor() ] )
{3, 6, 12}
sage: # the first few (six below) polynomials of "full" degree in the above factorization are:
sage: count = 0
....: for pol, mul in E.division_polynomial(97).factor():
....:     if pol.degree() < 12:
....:         continue
....:     count += 1
....:     print pol
....:     if count > 5:
....:         break
....: 
x^12 + 10*x^10 + 36*x^9 + 90*x^8 + 16*x^7 + 60*x^6 + 89*x^5 + 19*x^4 + 36*x^3 + 66*x^2 + 13*x + 80
x^12 + 45*x^10 + 36*x^9 + 20*x^8 + 72*x^7 + 60*x^6 + 77*x^5 + 34*x^4 + 36*x^3 + 49*x^2 + 7*x + 80
x^12 + 47*x^10 + 52*x^9 + 26*x^8 + 29*x^7 + 75*x^6 + 19*x^5 + 30*x^4 + 83*x^3 + 30*x^2 + 102*x + 87
x^12 + 48*x^10 + 36*x^9 + 96*x^8 + 15*x^7 + 60*x^6 + 40*x^5 + 50*x^4 + 36*x^3 + 91*x^2 + 83*x + 80
x^12 + 57*x^10 + 52*x^9 + 63*x^8 + 79*x^7 + 75*x^6 + 50*x^5 + 32*x^4 + 83*x^3 + 41*x^2 + 47*x + 87
x^12 + 102*x^10 + 52*x^9 + 14*x^8 + 98*x^7 + 75*x^6 + 34*x^5 + 41*x^4 + 83*x^3 + 32*x^2 + 57*x + 87

and the total check:

sage: F
Finite Field of size 103
sage: F12.<a> = GF(p^12)
sage: a.minpoly()
x^12 + x^8 + 74*x^7 + 23*x^6 + 94*x^5 + 20*x^4 + 81*x^3 + 29*x^2 + 88*x + 5
sage: E12 = E.base_extend(F12)
sage: E12
Elliptic Curve defined by y^2 = x^3 + 102 over Finite Field in a of size 103^12
sage: E12.order().factor()
2^6 * 3^4 * 7^2 * 13^2 * 31 * 37^2 * 73 * 97^2 * 109 * 10453

and the factor $97^2$ shows we have a full $E[n]$ over $F':=\Bbb F_p^{12}$.

---

Now the slides are introducing the Tate pairing, $$ \hat e:E[n]\times E[n]\to \underbrace{(\Bbb F_{p^{12}})^\times[n]}_{:=\Bbb G_T}\ , $$ where i suppose that the index $T$ stays for Tate. Since $(\Bbb F_{p^{12}})^\times$ is cyclic of order $p^{12}-1$, and $n$ divides simply this number, we expect $n=97$ such values. We can compute them explicitly.

Now things get precipitated. We have a beautiful pair, we pair two equally footed points $P,Q\in E[n]$, and get a scalar $\hat e(P,Q)$, but the paper needs for the applications an asymmetrical setting, so inside of $E[n]\times E[n]$ we single out a subgroup with bolded notation, $\Bbb G_1\times \Bbb G_2$. Here,

• $\Bbb G_1=E(F)=E(\Bbb F_p)=E[n](\Bbb F_p)=E(\Bbb F_p)[n]$, nothing special,
• and $\Bbb G_2$ is by definition first "any other subgroup of order $E(F')[n]$", but two lines below it is the "Trace zero subgroup..." from the OP.

So let it be this trace zero subgroup in the sequel.

---

---

To have a clear situation, let us compute $E(F')[n]$ and this trace zero subgroup $\Bbb G_2$ inside it. Since the answer to the stated question starts here, we also make a tabula rasa and type the code from the scratch.

sage: F = GF(103)
sage: F12.<a> = GF(103^12)
sage: E = EllipticCurve(F, [0, 5])
sage: E12 = EllipticCurve(F12, [0, 5])
sage: xList = E.division_polynomial(n).roots(ring=F12, multiplicities=False)
sage: len(xList), 2*len(xList), E12.order()
(4704, 9408, 1425760886847297042753984)
sage: len(xList), 2*len(xList), 97^2, E12.order().factor()
(4704,
 9408,
 9409,
 2^6 * 3^4 * 7^2 * 13^2 * 31 * 37^2 * 73 * 97^2 * 109 * 10453)
sage: # let us associate a point P0 for the first element in the xList
sage: x0 = xList[0]
sage: y0 = sqrt( x0^3 + 5 )
sage: P0 = E12.point( (x0, y0) )
sage: P0.order()
97

sage: points = [ E12(0), ]    # and we extend
sage: for x in xList:
....:     y = sqrt( x^3 + 5 )
....:     points.append( E12.point( (x, +y) ) )
....:     points.append( E12.point( (x, -y) ) )
....:     
sage: len(points)
9409

We have now the $n^2=9409$ in the hand. For each point $P$ in the list we compute $$ \operatorname{Tr}(P) := P+\pi P+\pi^2 P+\dots +\pi^{11}P\ . $$ In case the result is zero, the zero in $E(F')$, we put it in a separate list.

sage: def trace(P):
....:     if P == E12(0):
....:         return 0
....:     x,y = P.xy()
....:     return sum( [ E12.point( (x^(p^j), y^(p^j)) ) for j in [0..11] ] )
....: 
sage: points_of_trace_zero = []
sage: for P in points:
....:     if trace(P) == E12(0):
....:         points_of_trace_zero.append(P)
....:
sage: len(points_of_trace_zero)
97 

So we obtain indeed $97$ points.

Note that the points are not defined over $\Bbb F_p$. For instance:

sage: P = points_of_trace_zero[33]
sage: P.xy()
(82*a^11 + 14*a^10 + 98*a^9 + 73*a^8 + 78*a^7 + 93*a^6 + 3*a^5 + 57*a^4 + 100*a^3 + 45*a^2 + 31*a + 82,
 13*a^11 + 14*a^10 + 84*a^9 + 79*a^8 + 56*a^7 + 42*a^6 + 45*a^5 + 71*a^4 + 88*a^3 + 65*a^2 + 18*a + 58)
sage: x, y = P.xy()
sage: x.minpoly()
x^6 + 3*x^3 + 96
sage: y.minpoly()
x^4 + 96*x^2 + 3

and here is the full list of the minimal polynomials for the $x$-component of points in $\Bbb G_2$:

sage: set( [ P.xy()[0].minpoly() for P in points_of_trace_zero if P != E12(0) ] )
{x^6 + 3*x^3 + 96,
 x^6 + 47*x^3 + 82,
 x^6 + 58*x^3 + 21,
 x^6 + 69*x^3 + 99,
 x^6 + 79*x^3 + 71,
 x^6 + 93*x^3 + 33,
 x^6 + 94*x^3 + 53,
 x^6 + 99*x^3 + 33}

This answers by example the present question. However... this is the begin of the story, in the slides there is mentioned without any (not even a vague) hint the existence of a monomorphism from some twist of $E$, which maps the $\Bbb F_p$-rational points of the twist to $\Bbb G_2$.

(If some reference to this is provided, i will fill in the code to compute this.)

---

For bigger values of $p,n$, the above code may not finish in time. However, for this situation the code and the constructed examples can be extended and analyzed to get deeper into the structure.