#8558: add a fast gcd algorithm for univariate polynomials over absolute number
fields
------------------------------------------------+---------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.8
Component: algebra | Resolution:
Keywords: gcd, pari, ntl, number field | Work issues:
Report Upstream: N/A | Reviewers: Jeroen Demeyer
Authors: Luis Felipe Tabera Alonso | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------+---------------------------
Comment (by lftabera):
Back to business.
I have updated the patch with Jeroen's suggestions. Still I have to do
something with
{{{
#Experimental bound IMPROVE
p = ZZ(3+min(2**255,
(max(map(abs,Bound.list())).n()**(0.4)).floor())).next_prime(proof=False)
}}}
p is the first prime to perform a modular gcd. If p=2, we will have to use
a lot of primes and will be inefficient. On the other hand, if p is too
big, we lose the advantages of modular gcd. So we have to give a sane,
intermediate default.
The prime above is based on some experiments I made two years ago, the
idea is to use a prime such that we will have to use few modular gcd, but
limiting our stating prime to the interval `[3, 2^255]`.
Ideas welcomed.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8558#comment:21>
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.
