#8335: Finite Field lattices
------------------------------------------------+---------------------------
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:
------------------------------------------------+---------------------------
Changes (by jpflori):
* status: needs_info => needs_review
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.
>
> __APPLY__
>
> 1. [attachment:trac_8335-pseudo_conway-5.10.b3.patch]
> 1. [attachment:trac_8335-finite_field_coerce-5.8.b0.patch]
> 1. [attachment:trac_8335-fixes-5.8.b0.patch]
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__
1. [attachment:trac_8335-pseudo_conway-5.10.b3.patch]
1. [attachment:trac_8335-finite_field_coerce-5.8.b0.patch]
1. [attachment:trac_8335-fixes-5.11.b1.patch]
--
Comment:
There was some actual bug in the code which triggered the computation of
the pseudo-Conway polynomials tree twice in the case where the extension
degree was prime.
First the way it should, and then using the same arguments as in the case
where this degree is not prime which at some point triggered the
computation of the power of modular integer with a small modulus and a
huge exponent and PARI rants when you do that;
just try
{{{
Mod(3,5)._pari_()**28172187218728127182718271821982918291829182918291
}}}
So the newly uploaded patch makes it so we only build the tree once as we
always should have, and at least in Luca's example it prevents PARI rants
to get on the screen.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8335#comment:51>
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.
