#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-4.7.2
Component: algebra | Keywords: gcd, pari, ntl, number field
Work_issues: | Upstream: N/A
Reviewer: | Author: Luis Felipe Tabera Alonso
Merged: | Dependencies:
---------------------------+------------------------------------------------
Comment(by jdemeyer):
Several comments:
1. Why the name `lift_pm()`? In PARI, this function is called
`centerlift()` which is more understandable in my opinion. On the other
hand, having the name ''begin'' with `lift` is more friendly for TAB-
completion, so why not `lift_centered` or something?
2. A special class for polynomials over number fields looks like a good
idea, but please put it in a separate file `polynomial_number_field.pyx`
instead of adding to `polynomial_element_generic.pyx`.
3. I have a hard time understand the text below. What is `c`? What is
`n`? Probably "reduction" is a better word than "project". And I also
think the name `K` for a polynomial ring is badly chosen:
{{{
def lift_to_poly_QQ(self,K):
"""
Compute a lift of poly to K.
INPUT:
- K: an univariate polynomial ring over an absolute number field
QQ[a].
In order to make sense of this algorithm, the minimum polynomial
of 'a'
should project onto `c` modulo `m`.
OUTPUT:
-A polynomial in QQ[a] such that its projection coefficientwise is
poly.
This algorithm uses rational reconstruction, so it may fail.
}}}
4. Why `_gcd()` instead of `gcd()`?
5. Add some tests using the global `gcd()` function instead of always
calling your `_gcd()` method.
6. Thanks to #11904, the line
{{{
h1 = pari([coeff._pari_('y') for coeff in self.list()]).Polrev()
}}}
can be changed to
{{{
h1 = pari(self)
}}}
7. This looks very fishy:
{{{
#Experimental bound IMPROVE
}}}
8. With
{{{
p = p.next_prime(False)
}}}
do you mean
{{{
p = p.next_prime(proof=False)
}}}
which is much clearer?
9. I believe the keyword argument `algoritm=` is usually used instead of
`method =` (note also the spacing!).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8558#comment:18>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
