#8558: add a fast gcd algorithm for univariate polynomials over absolute number
fields
-------------------------------------+-------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: algebra | Resolution:
Keywords: gcd, pari, ntl, | Merged in:
number field |
Authors: Luis Felipe | Reviewers: Jeroen Demeyer
Tabera Alonso |
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/lftabera/ticket/8558 | 5cfbce8851be4af6fceba9a37599b1150135540e
Dependencies: #14186, #15803, | Stopgaps:
#15804 |
-------------------------------------+-------------------------------------
Changes (by lftabera):
* status: needs_work => needs_review
Comment:
It looks that Pari is not really using a modular algorithm...
In any case, I have fixed the documentation, I have also fixed some
heuristic assumptions about the primes. Do not use proof=False and be more
conservative about the size of the primes. In principle, with proof=False
we could try a composite number such that the gcd in the residue ring
success but some prime factors are good and some are bad. Not sure if this
is possible. Also, chinese remainder could potentially fail, in this case
I think that can only happens if the gcd is already unfeasible by any
method. But let's be conservative and use only failproof methods.
--
Ticket URL: <https://trac.sagemath.org/ticket/8558#comment:60>
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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
