Dear all,
I've finally started to work on this, and as already pointed out
earlier it's under trac ticket #4000. Martin Albrecht implemented a
prototype to help me get started and I've now looked at it in some
more details and implemented almost all the functionality, except for
the three methods celement_pow, celement_gcd, celement_xgcd. There
are a few questions that I have about this:
(1) Implementation of exponentiation:
The method signature in fmpq_poly_linkage.pxi is "celement_pow
(fmpq_poly_t res, fmpq_poly_t x, long e, fmpq_poly_t modulus, unsigned
long n)". I know how to implement this in the case no modulus is
given, but I am slightly uneasy about the case when a modulus is
given. Looking at the docstring of the corresponding method in
zmod_poly_linkage.pxi shows the following example:
sage: pow(f, -2, g)
1/(15328*x + 6968)
sage: (f^2 % g)^-1
1/(15328*x + 6968)
I guess the second output is as expected, one first reduces the
polynomial f^2 of (Z/nZ)[x] modulo the polynomial g of (Z/nZ)[x] in
the canonical way, and then places the inverse in the fraction field
(Z/nZ)(x), except perhaps in the case where the reduction is a unit,
although I am not sure whether this is checked. The two calls in the
example giving the same result suggests that this is also the way
modular exponentiation via "celement_pow(...)" should be implemented.
But at a first glance this seems strange. I think the "celement_pow
(...)" method should return the multiplicative inverse of f^2 in (Z/
nZ) [x] modulo the ideal generated by the polynomial g, lifted
canonically to (Z/nZ)[x], or raise an error if f^2 is not invertible.
Could someone please clarify how this method should be implemented?
(2) GCD and XGCD:
FLINT does provide gcd and xgcd methods for polynomials in Z[x], but I
am not quite sure if (and how) I can use these to compute the gcd and
xgcd of two polynomials in Q[x]. Could someone please comment on
this?
But FLINT does provide what is called pseudo-division in their manual,
giving division with remainder of polynomials in Q[x]. If I can't use
the gcd and xgcd methods from FLINT, I could use the above division
procedure from FLINT to implement gcd and xgcd myself, and then
compare the performance with the current implementation of polynomials
over the rationals.
(3) Testing:
I think we need two sets of test cases, one to check that everything
works as it should and gives correct results including some corner
cases, which I think I'll be happy to set up myself, and another set
of useful polynomials for performance comparisons, which I am hoping
someone else can suggest.
Many thanks,
Sebastian
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
