Opened 7 years ago

Closed 6 years ago

Last modified 5 years ago

#20284 closed enhancement (fixed)

A class to manage embedding between non-prime fields

Reported by: David Lucas Owned by:
Priority: major Milestone: sage-7.3
Component: finite rings Keywords:
Cc: Johan Rosenkilde, Jean-Pierre Flori, Luca De Feo Merged in:
Authors: David Lucas Reviewers: Arpit Merchant
Report Upstream: N/A Work issues:
Branch: 2492c31 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

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, non-prime 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 (22)

comment:1 Changed 7 years ago by David Lucas

Branch: u/dlucas/field_embedding

comment:2 Changed 7 years ago by David Lucas

Authors: David Lucas
Cc: Johan Rosenkilde Jean-Pierre Flori Luca De Feo added
Commit: 49cebeef342bec6763892c3d9d1029b94f852867
Status: newneeds_review

I pushed my code, and I open this ticket for review.


New commits:

49cebeeNew class to manage embeddings between non-prime fields

comment:3 Changed 7 years ago by David Lucas

By the way, as I'm not sure where to put my code, I left it (for now) in sage/coding...

comment:4 Changed 7 years ago by Johan Rosenkilde

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^(sm-1) is the basis of GF(p^(sm)) that Sage currently uses natively, then it is always the case that 1, beta, ..., beta^(m-1) 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[m-1]) in GF(p^s)^m, such that

    e = sum_{i=0}^{m-1} phi(v[i]) * beta^i

where phi is a given embedding from GF(p^s) into GF(p^(sm)).

Best, Johan

comment:5 Changed 7 years ago by git

Commit: 49cebeef342bec6763892c3d9d1029b94f85286738b77f9f34a7e3480b5656e557fcf9c0c2a6e732

Branch pushed to git repo; I updated commit sha1. New commits:

7ffd2c0Update to 7.3beta2
74a8c23representation_matrix is now a private method
4f4c0a6Changed names: Fqm over Fq is now designated as a relative finite field extension
87deebaChanged return value of big_field_representation
0eb1d5aChanged naming: small field -> relative field, big field -> absolute field
38b77f9Added method to check if an element of the absolute field is in the relative field under the embedding

comment:6 Changed 7 years ago by David Lucas

Milestone: sage-7.2sage-7.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 Changed 7 years ago by Vincent Delecroix

Two naive questions:

  • Why is this in sage/coding?
  • Why not extending the preceding existing embedding class?

Vincent

comment:8 in reply to:  7 ; Changed 7 years ago by Johan Rosenkilde

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 7 years ago by Vincent Delecroix

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 7 years ago by Jean-Pierre Flori

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 Changed 7 years ago by David Lucas

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 rank-metric 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 7 years ago by Johan Rosenkilde

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 7 years ago by git

Commit: 38b77f9f34a7e3480b5656e557fcf9c0c2a6e7322492c313523014a07d88bc9af3809b96bf595700

Branch pushed to git repo; I updated commit sha1. New commits:

311b960Added experimental warning for RelativeFiniteFieldExtension
2492c31Added relative_finite_field_extension to sage.coding's index.rst

comment:14 Changed 7 years ago by David Lucas

I added this experimental warning to the class.

I also added this module in sage.coding's index.

comment:15 Changed 6 years ago by Arpit Merchant

Reviewers: Arpit Merchant
Status: needs_reviewpositive_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 6 years ago by Volker Braun

Branch: u/dlucas/field_embedding2492c313523014a07d88bc9af3809b96bf595700
Resolution: fixed
Status: positive_reviewclosed

comment:17 Changed 5 years ago by Maarten Derickx

Commit: 2492c313523014a07d88bc9af3809b96bf595700

Was there ever a follow up ticket created?

comment:18 in reply to:  17 Changed 5 years ago by Vincent Delecroix

Replying to mderickx:

Was there ever a follow up ticket created?

I don't think so. At least the code is still there in sage/coding/relative_finite_field_extension.py.

<rant start> It is a pitty that this ticket has been merged despite my objections in comment:7. It should have definitely be a file in sage/rings/finite_field/ 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>

comment:19 Changed 5 years ago by Jean-Pierre Flori

So let's create one: #23828.

There is also the old and somehow useless #8751. And related works: https://github.com/wbhart/flint2/issues/366

comment:20 Changed 5 years ago by Johan Rosenkilde

The follow-up ticket is #21413. 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 /sage/rings/ 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 L/K.

The ticket #21413 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 L/K algebra and elements of K leading to (perhaps) unintuitive non-commutative behaviour. See the discussion on that ticket for a more precise description.

comment:21 Changed 5 years ago by Jean-Pierre Flori

Argh then let's already close #23828.

comment:22 Changed 5 years ago by Vincent Delecroix

See also #24170

Note: See TracTickets for help on using tickets.