Ask Your Question
2

Elliptic Curve over Tower of Finite Field

asked 2020-05-17 05:27:09 -0500

Taylor Huang gravatar image

updated 2020-05-17 14:43:59 -0500

So I was trying to construct a curve and compute arithmetics on different hierachy of extensions. The problem is, since in my application the characteristic $p$ is so large that the regular Fq.extension(degree) runs like forever. I'm not sure why but I could instead compute irr = PolynomialRing(Fq,'x').irreducible_element(degree) and then just do the extension extFq = Fq.extension(irr) by explicitly specifying a irreducible. However, my curve obtain by E.change_ring(extFq) would no longer be recognized over finite field and able to sample a random point. Thus the following snippet fails

q, degree = 6441726727896377540006619567673100761, 8
# q is some priori decided prime power and degree is roughly 8
Fq = GF(q)
E = EllipticCurve(Fq,[1,0])
irr = PolynomialRing(Fq,'x').irreducible_element(degree)
extFq = Fq.extension(irr)
extE = E.change_ring(extFq)
extE.random_element() #this fails

On another hand, if I simply specify the relative extension extFq = GF(q^degree) and use the relative extension RelativeFiniteFieldExtension to get the embedding, then I'm not sure how to specify the coersion explicitly while using E.change_ring.

p, degree = 2538055698343985819, 8
q  = p^2
Fq = GF(q)
E = EllipticCurve(Fq,[1,0])
irr = PolynomialRing(GF(p),'x').irreducible_element(2*degree)
extFq = GF(q^degree,'x',irr)
# we could obtain embedding by
# rel = RelativeFiniteFieldExtension(extFq,Fq)
E.change_ring(extFq) # error: no coersion

Is there any way to get around this?

edit retag flag offensive close merge delete

Comments

Could you please provide your code ?

tmonteil gravatar imagetmonteil ( 2020-05-17 06:24:42 -0500 )edit

@tmonteil I have edit and include the codes

Taylor Huang gravatar imageTaylor Huang ( 2020-05-17 09:29:30 -0500 )edit

Please provide minimal complete code that can be copy-pasted in a fresh Sage session.

Providing concrete values helps immensely by saving others the trouble of making lots of decisions.

This allows others to help even if they are not experts in that field of mathematics.

slelievre gravatar imageslelievre ( 2020-05-17 12:40:23 -0500 )edit

I've added runnable codes.

Taylor Huang gravatar imageTaylor Huang ( 2020-05-17 14:44:34 -0500 )edit

Why do you want to use change_ring? Why not define E over the big field directly?

rburing gravatar imagerburing ( 2020-05-18 12:57:15 -0500 )edit

2 answers

Sort by » oldest newest most voted
2

answered 2020-05-20 04:54:38 -0500

Taylor Huang gravatar image

updated 2020-05-20 06:41:21 -0500

It seems my question didn't raise enough attention. I would answer my own question, though.

To embed a curve into a larger field, simply use change_ring with specified morphisms. For my particular case

p, degree = 2538055698343985819, 8
q  = p^2
Fq = GF(q)
E = EllipticCurve(Fq,[1,0])
irr = PolynomialRing(GF(p),'x').irreducible_element(2*degree)
extFq = GF(q^degree,'x',irr)
# we could obtain embedding by
rel = RelativeFiniteFieldExtension(extFq,Fq)
E.change_ring(rel.embedding())
E.random_element()
edit flag offensive delete link more

Comments

Thanks for sharing your findings. Note that RelativeFiniteFieldExtension is not in the namespace, it should be imported as follows:

sage: from sage.coding.relative_finite_field_extension import RelativeFiniteFieldExtension
tmonteil gravatar imagetmonteil ( 2020-05-20 06:05:15 -0500 )edit
0

answered 2020-05-22 08:39:39 -0500

dan_fulea gravatar image

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…)

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-05-17 05:27:09 -0500

Seen: 103 times

Last updated: May 22