#8335: Finite Field lattices for (pseudo-)Conway polynomials
------------------------------------------------+---------------------------
Reporter: roed | Owner: AlexGhitza
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.11
Component: algebra | Resolution:
Keywords: days49 | Work issues:
Report Upstream: N/A | Reviewers: Jean-Pierre
Flori, Luca De Feo
Authors: David Roe, Jean-Pierre Flori | Merged in:
Dependencies: #13894 | Stopgaps:
------------------------------------------------+---------------------------
Comment (by jpflori):
Replying to [comment:73 pbruin]:
> Replying to [comment:72 jpflori]:
> > Beware that the last patch which contains my modification to the two
original patches by David changes quite a lot of thing.
> > In particular, I think that with it modulus contains the real modulus
as well and I use additional attributes to check for pseudo-Conway
construction.
>
> OK, I'll try to find out if and how my ideas about making the choice of
polynomial independently of the finite field implementation can be
harmonised with your patch. At first sight there does not seem to be a
huge clash. I am mostly worried about the use of strings like 'conwayz'
as a modulus, which really seems to be overloading this parameter too
much.
>
> > Also note that the real nice addition of this patch is mainly the
compatible embeddings.
>
> I agree that this is a very desirable thing to have, and it is also nice
to be able to simply type ``F = GF(p^n^)`` without having to care about
variable names and embeddings. I do think it is good to think carefully
about how exactly to accomplish this.
Agreed.
But it just happened I stumled upon this ticket which already looked
usable (and was two years old) and thought "oh, let's already get this in;
later on we can design better constructions of compatible embeddings and
get something more general and fast".
So I decided to postpone the design of a cool and fast system in #8751 and
only deal with "lattices using (pseudo) Conway polynomials" here.
It's better to have something than nothing.
>
> In particular, I am not sure if it is wise to say in the
documentation/specification that this compatibility is achieved using
(pseudo-)Conway polynomials, since different implementations are
imaginable. I am thinking of the standard models for finite fields by
Lenstra and de Smit, which are constructed in a way that does not seem to
be related to Conway polynomials.
>
I completely agree that using Conway polynomials is a no go as soon as you
quit fields of small cardinalities.
I've met Eric Rains who participated in the Magma implementation (or at
least the algos behind it) and he was nice enough to share with me a draft
describing the algos used.
De Feo and Schost and others are also producing nice paper on how to build
p- or l-adic towers of finite fields.
What is very nice is that they avoid linear algebra (what Magma may not
completely do).
> From a conceptual point of view, it is desirable that GF(p^n^) without
any arguments should refer to the unique subfield of cardinality p^n^
''inside a chosen algebraic closure'' of GF(p). This gives 'compatible
embeddings' the very simple meaning of 'inclusions within an algebraic
closure'.
>
> Such an algebraic closure could be implemented in different ways, for
example via (pseudo-)Conway polynomials; algebraic closures of GF(p)
resulting from different methods would be non-canonically isomorphic.
There might be a default choice that could change in the future, and the
user should be able to specify which algebraic closure should be taken.
>
I agree, so it makes sense to have a pseudo Conway implementation and
other ones later.
> Here is how I would hope a hypothetical future Sage session to look
like:
>
> {{{
> sage: p = 5
> sage: Fpbar = GF(p).algebraic_closure()
> sage: Fpbar
> Algebraic closure of Finite Field of size 5
> sage: Fa = GF(p^2, 'a')
> sage: Fa
> Finite field in a of size 5^2
> sage: is_subfield(Fa, Fpbar)
> False
> sage: Fb = GF(p^2)
> Subfield of size 5^2 of Algebraic closure of Finite Field of size 5
> sage: is_subfield(Fb, Fpbar)
> True
> sage: type(Fpbar)
> <class 'sage.rings.AlgebraicClosureFiniteField_pseudo_conway'>
> }}}
> Would something like this be easy to achieve once this ticket has been
implemented?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8335#comment:74>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
