Answer to (2) below. I am VERY please that someone is at last doing this!
On Sep 8, 1:27 am, Sebastian Pancratz <s...@pancratz.org> wrote: > 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? Easy: let f, g be nonzero polys in Q[x], divide by their contents (nonzero rationals) to get two primitive polys in Z[x]. Return the gcd of those. John > > 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 -~----------~----~----~----~------~----~------~--~---
