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
-~----------~----~----~----~------~----~------~--~---
