Oops, I misread. Please totally ignore my response.
On 9 Sep, 17:05, Bill Hart <goodwillh...@googlemail.com> wrote:
> On 8 Sep, 01:27, 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?
>
> Yes it does. Highly optimised versions of both in fact.
>
>
>
>
>
> > 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
-~----------~----~----~----~------~----~------~--~---
