Sage: Ticket #20284: A class to manage embedding between non-prime fields
https://trac.sagemath.org/ticket/20284
<p>
In Sage, there is no general mechanism to manage the embedding of elements of a finite extension field in one of its subfields.
</p>
<p>
We propose here a class which takes care of that.
</p>
<p>
Considering a big, non-prime field <code>Fqm</code> and one of its subfields <code>Fq</code>, this class is able to give either a polynomial or a vectorial representation of an element of <code>Fqm</code> in <code>Fq</code>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/20284
Trac 1.1.6dlucasFri, 25 Mar 2016 08:47:49 GMTbranch set
https://trac.sagemath.org/ticket/20284#comment:1
https://trac.sagemath.org/ticket/20284#comment:1
<ul>
<li><strong>branch</strong>
set to <em>u/dlucas/field_embedding</em>
</li>
</ul>
TicketdlucasFri, 25 Mar 2016 08:49:36 GMTstatus changed; cc, commit, author set
https://trac.sagemath.org/ticket/20284#comment:2
https://trac.sagemath.org/ticket/20284#comment:2
<ul>
<li><strong>cc</strong>
<em>jsrn</em> <em>jpflori</em> <em>defeo</em> added
</li>
<li><strong>commit</strong>
set to <em>49cebeef342bec6763892c3d9d1029b94f852867</em>
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>David Lucas</em>
</li>
</ul>
<p>
I pushed my code, and I open this ticket for review.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=49cebeef342bec6763892c3d9d1029b94f852867"><span class="icon"></span>49cebee</a></td><td><code>New class to manage embeddings between non-prime fields</code>
</td></tr></table>
TicketdlucasFri, 25 Mar 2016 08:54:51 GMT
https://trac.sagemath.org/ticket/20284#comment:3
https://trac.sagemath.org/ticket/20284#comment:3
<p>
By the way, as I'm not sure where to put my code, I left it (for now) in <code>sage/coding</code>...
</p>
TicketjsrnFri, 25 Mar 2016 09:54:04 GMT
https://trac.sagemath.org/ticket/20284#comment:4
https://trac.sagemath.org/ticket/20284#comment:4
<p>
Just to be precise: Sage already supports embedding a small field <code>GF(p^s)</code> into a larger one <code>GF(p^(sm))</code> (by using <code>Fsmall.extension(m, map=True)</code>). It also supports the inverse map (returned by the <code>section()</code> method on the embedding map).
</p>
<p>
The new functionality of this ticket is to support representing any <code>GF(p^(sm))</code> element in a basis over <code>GF(p^s)</code>. AFAIK, the current implementation supports this with only one particular choice of bases: if <code>1, beta, ..., beta^(sm-1)</code> is the basis of <code>GF(p^(sm))</code> that Sage currently uses natively, then it is always the case that <code>1, beta, ..., beta^(m-1)</code> is a basis of <code>GF(p^(sm))</code> over <code>GF(p^s)</code>. This is the basis employed by the current ticket.
</p>
<p>
More precisely, it gives a function that takes an element <code>e</code> in <code>GF(p^(sm))</code> and returns a vector <code>(v[0],...,v[m-1]) in GF(p^s)^m</code>, such that
</p>
<pre class="wiki"> e = sum_{i=0}^{m-1} phi(v[i]) * beta^i
</pre><p>
where <code>phi</code> is a given embedding from <code>GF(p^s)</code> into <code>GF(p^(sm))</code>.
</p>
<p>
Best,
Johan
</p>
TicketgitTue, 31 May 2016 14:48:52 GMTcommit changed
https://trac.sagemath.org/ticket/20284#comment:5
https://trac.sagemath.org/ticket/20284#comment:5
<ul>
<li><strong>commit</strong>
changed from <em>49cebeef342bec6763892c3d9d1029b94f852867</em> to <em>38b77f9f34a7e3480b5656e557fcf9c0c2a6e732</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7ffd2c0a9f3bd5e36b3b56aab4f66896dfecd0d3"><span class="icon"></span>7ffd2c0</a></td><td><code>Update to 7.3beta2</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=74a8c237c130e173b527dcd8e8597efa16a38ee8"><span class="icon"></span>74a8c23</a></td><td><code>representation_matrix is now a private method</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4f4c0a677ec818771049d35e870abc1198c0c8d7"><span class="icon"></span>4f4c0a6</a></td><td><code>Changed names: Fqm over Fq is now designated as a relative finite field extension</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=87deeba348f41603a49d85d0d0810b00bf6d5046"><span class="icon"></span>87deeba</a></td><td><code>Changed return value of big_field_representation</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0eb1d5a0956026fe2dbf16b2daf196bfd8f26f93"><span class="icon"></span>0eb1d5a</a></td><td><code>Changed naming: small field -> relative field, big field -> absolute field</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=38b77f9f34a7e3480b5656e557fcf9c0c2a6e732"><span class="icon"></span>38b77f9</a></td><td><code>Added method to check if an element of the absolute field is in the relative field under the embedding</code>
</td></tr></table>
TicketdlucasTue, 31 May 2016 14:51:05 GMTmilestone changed
https://trac.sagemath.org/ticket/20284#comment:6
https://trac.sagemath.org/ticket/20284#comment:6
<ul>
<li><strong>milestone</strong>
changed from <em>sage-7.2</em> to <em>sage-7.3</em>
</li>
</ul>
<p>
Hello,
</p>
<p>
I made some changes to the class:
</p>
<ul><li>I completely changed its nomenclature, which is now based on the one defined for <a class="ext-link" href="http://doc.sagemath.org/html/en/thematic_tutorials/explicit_methods_in_number_theory/nf_orders.html#relative-extensions"><span class="icon"></span>relative extensions</a>.
</li><li>I changed the behaviour of some methods.
</li><li>I added a method to check if an element of the "big field" is in the relative field under the embedding.
</li></ul><p>
This is still open for review.
</p>
<p>
Best,
</p>
<p>
David
</p>
TicketvdelecroixTue, 31 May 2016 16:28:32 GMT
https://trac.sagemath.org/ticket/20284#comment:7
https://trac.sagemath.org/ticket/20284#comment:7
<p>
Two naive questions:
</p>
<ul><li>Why is this in sage/coding?
</li><li>Why not extending the preceding existing embedding class?
</li></ul><p>
Vincent
</p>
TicketjsrnTue, 31 May 2016 19:54:39 GMT
https://trac.sagemath.org/ticket/20284#comment:8
https://trac.sagemath.org/ticket/20284#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/20284#comment:7" title="Comment 7">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Two naive questions:
</p>
<ul><li>Why is this in sage/coding?
</li><li>Why not extending the preceding existing embedding class?
</li></ul></blockquote>
<p>
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.
</p>
<p>
Incidentally, will you be coming for SD75?
</p>
TicketvdelecroixTue, 31 May 2016 20:00:12 GMT
https://trac.sagemath.org/ticket/20284#comment:9
https://trac.sagemath.org/ticket/20284#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/20284#comment:8" title="Comment 8">jsrn</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/20284#comment:7" title="Comment 7">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Two naive questions:
</p>
<ul><li>Why is this in sage/coding?
</li><li>Why not extending the preceding existing embedding class?
</li></ul></blockquote>
<p>
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.
</p>
</blockquote>
<p>
Would make more sense with everything about finite field, no? That is to say <code>sage/rings/finite_rings/</code>.
</p>
<blockquote class="citation">
<p>
Incidentally, will you be coming for SD75?
</p>
</blockquote>
<p>
Sadly not. I will be in Chile at that time.
</p>
TicketjpfloriWed, 01 Jun 2016 06:42:17 GMT
https://trac.sagemath.org/ticket/20284#comment:10
https://trac.sagemath.org/ticket/20284#comment:10
<p>
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 <code>coding</code> first and move it later.
</p>
TicketdlucasWed, 01 Jun 2016 08:49:27 GMT
https://trac.sagemath.org/ticket/20284#comment:11
https://trac.sagemath.org/ticket/20284#comment:11
<p>
Hello,
</p>
<blockquote class="citation">
<p>
And I do agree it would nice to use such functionalities in a more general setting.
We could still put it in <code>coding</code> first and move it later.
</p>
</blockquote>
<p>
I would indeed prefer to put it in <code>coding</code> first, as it locks several very useful tickets for us (<a class="closed ticket" href="https://trac.sagemath.org/ticket/20039" title="enhancement: Subfield subcodes (closed: fixed)">#20039</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/20100" title="enhancement: A new structure for Cyclic codes (closed: fixed)">#20100</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/20335" title="enhancement: A new structure for BCH codes (closed: fixed)">#20335</a>) while it's not reviewed. Furthermore, we need it for our GSoC project on rank-metric codes.
</p>
<p>
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.
</p>
<p>
Best,
</p>
<p>
David
</p>
TicketjsrnWed, 01 Jun 2016 13:13:43 GMT
https://trac.sagemath.org/ticket/20284#comment:12
https://trac.sagemath.org/ticket/20284#comment:12
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
+1
</p>
TicketgitWed, 01 Jun 2016 13:35:53 GMTcommit changed
https://trac.sagemath.org/ticket/20284#comment:13
https://trac.sagemath.org/ticket/20284#comment:13
<ul>
<li><strong>commit</strong>
changed from <em>38b77f9f34a7e3480b5656e557fcf9c0c2a6e732</em> to <em>2492c313523014a07d88bc9af3809b96bf595700</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=311b960f9252d66a080e76fffd5d9ed475581c01"><span class="icon"></span>311b960</a></td><td><code>Added experimental warning for RelativeFiniteFieldExtension</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2492c313523014a07d88bc9af3809b96bf595700"><span class="icon"></span>2492c31</a></td><td><code>Added relative_finite_field_extension to sage.coding's index.rst</code>
</td></tr></table>
TicketdlucasWed, 01 Jun 2016 13:37:14 GMT
https://trac.sagemath.org/ticket/20284#comment:14
https://trac.sagemath.org/ticket/20284#comment:14
<p>
I added this experimental warning to the class.
</p>
<p>
I also added this module in <code>sage.coding</code>'s index.
</p>
TicketarpitdmWed, 08 Jun 2016 16:15:36 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/20284#comment:15
https://trac.sagemath.org/ticket/20284#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Arpit Merchant</em>
</li>
</ul>
<p>
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.
</p>
TicketvbraunThu, 09 Jun 2016 16:14:09 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/20284#comment:16
https://trac.sagemath.org/ticket/20284#comment:16
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/dlucas/field_embedding</em> to <em>2492c313523014a07d88bc9af3809b96bf595700</em>
</li>
</ul>
TicketmderickxFri, 08 Sep 2017 09:10:01 GMTcommit deleted
https://trac.sagemath.org/ticket/20284#comment:17
https://trac.sagemath.org/ticket/20284#comment:17
<ul>
<li><strong>commit</strong>
<em>2492c313523014a07d88bc9af3809b96bf595700</em> deleted
</li>
</ul>
<p>
Was there ever a follow up ticket created?
</p>
TicketvdelecroixSun, 10 Sep 2017 20:26:31 GMT
https://trac.sagemath.org/ticket/20284#comment:18
https://trac.sagemath.org/ticket/20284#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/20284#comment:17" title="Comment 17">mderickx</a>:
</p>
<blockquote class="citation">
<p>
Was there ever a follow up ticket created?
</p>
</blockquote>
<p>
I don't think so. At least the code is still there in <code>sage/coding/relative_finite_field_extension.py</code>.
</p>
<p>
<rant start>
It is a pitty that this ticket has been merged despite my objections in <a class="ticket" href="https://trac.sagemath.org/ticket/20284#comment:7" title="Comment 7">comment:7</a>. It should have definitely be a file in <code>sage/rings/finite_field/</code> so that people actually working with finite field would have noticed. Putting a blob of general purpose functionalities in a specialized repository is not the way to proceed. People are free to do that on their home git repository but would better avoid such practice in a large public open source software.
<rant end>
</p>
TicketjpfloriMon, 11 Sep 2017 08:54:47 GMT
https://trac.sagemath.org/ticket/20284#comment:19
https://trac.sagemath.org/ticket/20284#comment:19
<p>
So let's create one: <a class="closed ticket" href="https://trac.sagemath.org/ticket/23828" title="defect: Move embeddings of finite fields into the proper folder (closed: duplicate)">#23828</a>.
</p>
<p>
There is also the old and somehow useless <a class="new ticket" href="https://trac.sagemath.org/ticket/8751" title="defect: conversion between non-prime finite fields (new)">#8751</a>.
And related works: <a class="ext-link" href="https://github.com/wbhart/flint2/issues/366"><span class="icon"></span>https://github.com/wbhart/flint2/issues/366</a>
</p>
TicketjsrnMon, 11 Sep 2017 08:57:56 GMT
https://trac.sagemath.org/ticket/20284#comment:20
https://trac.sagemath.org/ticket/20284#comment:20
<p>
The follow-up ticket is <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/21413" title="enhancement: A class for ring extensions (needs_work)">#21413</a>. It was created shortly after SD75 following discussion between Xavier Caruso, Luca De Feo, Nicola Thierry, Bruno Grenet and myself. The main difficulty in moving the code to <code>/sage/rings/</code> is to find the proper and general interface. Xavier in particular came up with centering these kinds of embeddings around the algebra induced by the field extension <code>L/K</code>.
</p>
<p>
The ticket <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/21413" title="enhancement: A class for ring extensions (needs_work)">#21413</a> then stalled because of lack of time, I think, and because we hit a snag wrt. implicit coercion vs use of multiplication btw. elements of the <code>L/K</code> algebra and elements of <code>K</code> leading to (perhaps) unintuitive non-commutative behaviour. See the discussion on that ticket for a more precise description.
</p>
TicketjpfloriMon, 11 Sep 2017 08:59:58 GMT
https://trac.sagemath.org/ticket/20284#comment:21
https://trac.sagemath.org/ticket/20284#comment:21
<p>
Argh then let's already close <a class="closed ticket" href="https://trac.sagemath.org/ticket/23828" title="defect: Move embeddings of finite fields into the proper folder (closed: duplicate)">#23828</a>.
</p>
TicketvdelecroixSun, 12 Nov 2017 11:20:07 GMT
https://trac.sagemath.org/ticket/20284#comment:22
https://trac.sagemath.org/ticket/20284#comment:22
<p>
See also <a class="closed ticket" href="https://trac.sagemath.org/ticket/24170" title="enhancement: Extend vector_space method to arbitrary subfields (closed: fixed)">#24170</a>
</p>
Ticket