Opened 13 months ago
Closed 11 months ago
#20284 closed enhancement (fixed)
A class to manage embedding between nonprime fields
Reported by:  dlucas  Owned by:  

Priority:  major  Milestone:  sage7.3 
Component:  finite rings  Keywords:  
Cc:  jsrn, jpflori, defeo  Merged in:  
Authors:  David Lucas  Reviewers:  Arpit Merchant 
Report Upstream:  N/A  Work issues:  
Branch:  2492c31 (Commits)  Commit:  2492c313523014a07d88bc9af3809b96bf595700 
Dependencies:  Stopgaps: 
Description
In Sage, there is no general mechanism to manage the embedding of elements of a finite extension field in one of its subfields.
We propose here a class which takes care of that.
Considering a big, nonprime field Fqm
and one of its subfields Fq
, this class is able to give either a polynomial or a vectorial representation of an element of Fqm
in Fq
.
Change History (16)
comment:1 Changed 13 months ago by
 Branch set to u/dlucas/field_embedding
comment:2 Changed 13 months ago by
 Cc jsrn jpflori defeo added
 Commit set to 49cebeef342bec6763892c3d9d1029b94f852867
 Status changed from new to needs_review
comment:3 Changed 13 months ago by
By the way, as I'm not sure where to put my code, I left it (for now) in sage/coding
...
comment:4 Changed 13 months ago by
Just to be precise: Sage already supports embedding a small field GF(p^s)
into a larger one GF(p^(sm))
(by using Fsmall.extension(m, map=True)
). It also supports the inverse map (returned by the section()
method on the embedding map).
The new functionality of this ticket is to support representing any GF(p^(sm))
element in a basis over GF(p^s)
. AFAIK, the current implementation supports this with only one particular choice of bases: if 1, beta, ..., beta^(sm1)
is the basis of GF(p^(sm))
that Sage currently uses natively, then it is always the case that 1, beta, ..., beta^(m1)
is a basis of GF(p^(sm))
over GF(p^s)
. This is the basis employed by the current ticket.
More precisely, it gives a function that takes an element e
in GF(p^(sm))
and returns a vector (v[0],...,v[m1]) in GF(p^s)^m
, such that
e = sum_{i=0}^{m1} phi(v[i]) * beta^i
where phi
is a given embedding from GF(p^s)
into GF(p^(sm))
.
Best, Johan
comment:5 Changed 11 months ago by
 Commit changed from 49cebeef342bec6763892c3d9d1029b94f852867 to 38b77f9f34a7e3480b5656e557fcf9c0c2a6e732
Branch pushed to git repo; I updated commit sha1. New commits:
7ffd2c0  Update to 7.3beta2

74a8c23  representation_matrix is now a private method

4f4c0a6  Changed names: Fqm over Fq is now designated as a relative finite field extension

87deeba  Changed return value of big_field_representation

0eb1d5a  Changed naming: small field > relative field, big field > absolute field

38b77f9  Added method to check if an element of the absolute field is in the relative field under the embedding

comment:6 Changed 11 months ago by
 Milestone changed from sage7.2 to sage7.3
Hello,
I made some changes to the class:
 I completely changed its nomenclature, which is now based on the one defined for relative extensions.
 I changed the behaviour of some methods.
 I added a method to check if an element of the "big field" is in the relative field under the embedding.
This is still open for review.
Best,
David
comment:7 followup: ↓ 8 Changed 11 months ago by
Two naive questions:
 Why is this in sage/coding?
 Why not extending the preceding existing embedding class?
Vincent
comment:8 in reply to: ↑ 7 ; followup: ↓ 9 Changed 11 months ago by
Replying to vdelecroix:
Two naive questions:
 Why is this in sage/coding?
 Why not extending the preceding existing embedding class?
Because we did not know where to put it, and we didn't get input from anyone. We need the functionality for several things in sage/coding, so we just wanted to add it. And it's on the agenda for Sage Days 75 to merge it much more sensibly with the rest of Sage.
Incidentally, will you be coming for SD75?
comment:9 in reply to: ↑ 8 Changed 11 months ago by
Replying to jsrn:
Replying to vdelecroix:
Two naive questions:
 Why is this in sage/coding?
 Why not extending the preceding existing embedding class?
Because we did not know where to put it, and we didn't get input from anyone. We need the functionality for several things in sage/coding, so we just wanted to add it. And it's on the agenda for Sage Days 75 to merge it much more sensibly with the rest of Sage.
Would make more sense with everything about finite field, no? That is to say sage/rings/finite_rings/
.
Incidentally, will you be coming for SD75?
Sadly not. I will be in Chile at that time.
comment:10 Changed 11 months ago by
I'll be there at sd75.
And I do agree it would nice to use such functionalities in a more general setting.
We could still put it in coding
first and move it later.
comment:11 followup: ↓ 12 Changed 11 months ago by
Hello,
And I do agree it would nice to use such functionalities in a more general setting. We could still put it in
coding
first and move it later.
I would indeed prefer to put it in coding
first, as it locks several very useful tickets for us (#20039, #20100, #20335) while it's not reviewed. Furthermore, we need it for our GSoC project on rankmetric codes.
I can put an experimental warning in it: this way, we will be able to move it later on without being worried by deprecation warnings.
Best,
David
comment:12 in reply to: ↑ 11 Changed 11 months ago by
I can put an experimental warning in it: this way, we will be able to move it later on without being worried by deprecation warnings.
+1
comment:13 Changed 11 months ago by
 Commit changed from 38b77f9f34a7e3480b5656e557fcf9c0c2a6e732 to 2492c313523014a07d88bc9af3809b96bf595700
comment:14 Changed 11 months ago by
I added this experimental warning to the class.
I also added this module in sage.coding
's index.
comment:15 Changed 11 months ago by
 Reviewers set to Arpit Merchant
 Status changed from needs_review to positive_review
I went through the reviewer's checklist and all the tests pass. The naming conventions are quite suitable and make it easier to interpret the functions. Giving it a positive review.
comment:16 Changed 11 months ago by
 Branch changed from u/dlucas/field_embedding to 2492c313523014a07d88bc9af3809b96bf595700
 Resolution set to fixed
 Status changed from positive_review to closed
I pushed my code, and I open this ticket for review.
New commits:
New class to manage embeddings between nonprime fields