#8335: Finite Field lattices
-------------------------------+--------------------------------------------
Reporter: roed | Owner: AlexGhitza
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-5.8
Component: algebra | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: David Roe | Merged in:
Dependencies: | Stopgaps:
-------------------------------+--------------------------------------------
Changes (by jpflori):
* status: needs_work => needs_info
* milestone: sage-5.7 => sage-5.8
Old description:
> Implements coercion within lattices of finite fields lying above the same
> prime.
>
> {{{
> sage: k = GF(9)
> sage: l = GF(27)
> sage: x = k.gen() + l.gen(); x
> z6^5 + 2*z6^4 + 2*z6^3 + z6^2 + 2*z6 + 1
> sage: x.parent()
> Finite Field in z6 of size 3^6
> }}}
>
> This feature is implemented for fields outside the range of the Conway
> polynomial database by the implementation of a function for finding
> pseudo-Conway polynomials: polynomials that satisfy all of the algebraic
> constraints on Conway polynomials without the lexicographic constraint
> that imposes uniqueness.
>
> Finite fields no longer require an explicit variable name (though they
> still accept one). If a variable name is given, then outside the range
> of the Conway polynomial database a random or sparse polynomial is used
> for speed reasons; if no variable name is given then either a Conway
> polynomial or pseudo-Conway polynomial is used.
>
> Also adds methods `any_root` and `squarefree_decomposition` to
> polynomials over finite fields.
>
> Depends on #8218, #8332, #7880, #7883, #8333, #8334
New description:
Implements coercion within lattices of finite fields lying above the same
prime.
{{{
sage: k = GF(9)
sage: l = GF(27)
sage: x = k.gen() + l.gen(); x
z6^5 + 2*z6^4 + 2*z6^3 + z6^2 + 2*z6 + 1
sage: x.parent()
Finite Field in z6 of size 3^6
}}}
This feature is implemented for fields outside the range of the Conway
polynomial database by the implementation of a function for finding
pseudo-Conway polynomials: polynomials that satisfy all of the algebraic
constraints on Conway polynomials without the lexicographic constraint
that imposes uniqueness.
Finite fields no longer require an explicit variable name (though they
still accept one). If a variable name is given, then outside the range of
the Conway polynomial database a random or sparse polynomial is used for
speed reasons; if no variable name is given then either a Conway
polynomial or pseudo-Conway polynomial is used.
Also adds methods `any_root` and `squarefree_decomposition` to polynomials
over finite fields.
Depends on #8218, #8332, #7880, #7883, #8333, #8334.
__APPLY__
*[attachment:trac_8335-pseudo_conway-5.7.b3.patch]
*[attachment:trac_8335-finite_field_coerce-5.7.b3.patch]
*[attachment:trac_8335-doc-5.7.b3.patch]
--
Comment:
These patches were quite old and things have moved around since they were
written.
As a consequence, part of the old patches now apply to different files,
that is the case of the NTL GF2E implementation which has been split in a
Python and a Cython file.
Some pseudo Conway polys changed so that two doctests now fail (not
corrected in the patches cause I did not take the time to think about it,
feel free to do it).
As these pseudo Conway polynomials are not unique, I'm not sure if the
procedure to generate them is deterministic or to which point randomness
comes into play and if the failing doctests are just due to some routine
called during the generation which may give a different result since the
patches were originally written.
Not really sure how to cast restriction on the is_square and
squarefree_decomposition methods, nor what I've changed makes sense, I've
come up with this quickly, feel free to correct it.
The basic problem was that now Sage supports function fields where we have
no p-th roots and that raised an AttributeError when calling is_square
which called squarefree_decomposition in some doctests.
The doc now builds ok and looks nice (although I did not have LaTeX on my
computer), but may need some revamping.
Nonetheless it would be great to get this in quickly.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8335#comment:14>
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
