Elliptic Curve over Tower of Finite Field

edit

I will write some words on the question. This is not exactly an answer to the question in a strict sense. It is rather an answer to a rephrased question. Please let me explain. We often use sage, as it is now, to solve problems in the mathematical realm. We can solve only "computational problems". Very often we have to take the decision of rephrasing the story either in the mathematical world, or in the programatical world (sage), to have a better fit or a better run time for both input and output. A main rule of keeping things simple, stupid on the programatical world is to use what we have there, and do not expect too much magic. So what we have in this case? We have random elements when the curve is defined over the bigger field, ok, let us take them. We do not have a coercion, a transport from the rational points of the curve E defined over Fq$\cong\Bbb F_{q^2}\cong\Bbb F_{p^2}$ to the rational points of the "same curve" defined over the bigger field $\cong\Bbb F_{q^8}\cong\Bbb F_{p^{16}}$ ? OK, we do not have it. But when we write down this sentence, we already have the reason. We have to construct the needed fields. Which more or less do have corresonding transport of elements.

In this case, i can see only one problem when working directly with E defined directly over the bigger field with $p^{16}$ elements, the one of "identifiying" or working with rational points that are defined over smaller fields. This is a problem much easier to solve (in a structural way).

Here is some code for fixing a setting to work inside.

p = 2538055698343985819
q, Q = p^2, p^16
# q, degree = 6441726727896377540006619567673100761, 8
# q is some priori decided prime power and degree is roughly 8

F = GF(p)
R.<x> = PolynomialRing(F)

Fq.<a> = GF(q)
FQ.<b> = GF(Q)

f = Fq.modulus()
g = FQ.modulus()

E  = EllipticCurve( F, [1, 0])
Eq = EllipticCurve(Fq, [1, 0])
EQ = EllipticCurve(FQ, [1, 0])

PQ = EQ.random_element()

# move points from E to EQ...
P = E.random_point()
EQP = EQ(P)
print(f"P   = {P}")
print(f"EQP = {EQP}")

S = Eq.random_element()

After a copy+paste into the ipython interpreter of sage, we have all we need...

P   = (1737516953789135143 : 2302365341466161118 : 1)
EQP = (1737516953789135143 : 2302365341466161118 : 1)

So we can easily move $F$-rational points of $E\ :\ y^2 = x^3 + x$, $E$ being seen over $F=\Bbb F_p$ to points over the bigger field. This is done "by magic", i would not expect such a behavior. I am not showing PQ because it would fill in some lines without need.

So the only problem remained (that i see) is to move a point in $E(\Bbb F_{p^2})$ to a point in $E(\Bbb F_{p^{16}})$. Usually, i am doing this in either way...

• construct with own bare hands $K=\Bbb F_{p^2})=F(a)$, $L=\Bbb F_{p^{16}})=F(b)$, then pick an element $A$ in $L$ having the same minimal polynomial as $a$, this defines a map $K\to L$, use this map at field level on components of points, or

• ask sage for an embeeding $\phi$ of $K$ into $L$ and use it componentwise on the points.

Illustrating sage dialog, for the latter version, because it is structurally simpler:

sage: Fq                                                                                                 
Finite Field in a of size 2538055698343985819^2
sage: FQ                                                                                                 
Finite Field in b of size 2538055698343985819^16
sage: H = Fq.Hom(FQ)                                                                                     
sage: H                                                                                                  
Set of field embeddings from Finite Field in a of size 2538055698343985819^2 to Finite Field in b of size 2538055698343985819^16
sage: len(H)                                                                                             
2

sage: phi = H[0]                                                                                         
sage: phi                                                                                                
Ring morphism:
  From: Finite Field in a of size 2538055698343985819^2
  To:   Finite Field in b of size 2538055698343985819^16
  Defn: a |--> 220112346125570156*b^15 + 1139081959449245502*b^14 + ....

(Result was manually truncated...)

Now we can take a point $S$ over $K$, and move it as a point over $L$...

sage: S = Eq.random_point()                                                                              
sage: xS, yS, zS = S                                                                                     
sage: EQ.point( (phi(xS), phi(yS), phi(zS)) )                                                            
(1794615948316880992*b^15 + 2255153724174906853*b^14 + 687338701198968153*b^13 +

(Something like EQ( [ phi(comp) for comp in S ] ) would also work, but this is unreadable and ununderstandable... I usually keep things in easy thinking and notation.)

For the first version, we could define $A$ to be one of the roots of the minimal polynomial f of a considered inside L...

sage: A = f.roots(ring=FQ, multiplicities=False)[0]                                                      
sage: A == phi(a)                                                                                        
True

and as seen, this choice of A corresponds to phi(a). Then we could define phi with bare hands.

The moral is: Work in the easy framework. If we need only the random_element method, then go directly there and work over the bigger field (only) avoiding towers of fields. If some intermediate field information is still needed, then still work in the bigger field, try to get needed subfield information programatically.

(Many questions related to sage are caused by an existing magic in a special situation, and there is somehow an expectation of having it in all cases for granted. People almost never look into the final code to see how hard the magic is obtained when we have it. And in 1% of the cases they really invest own effort to extend the magic. Less cases involve people getting involved…)