#19611: Error in gcd for polynomials modulo p^n
-------------------------------------------------+-------------------------
Reporter: roed | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.10
Component: algebra | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: Reported upstream. No | Work issues:
feedback yet. | Commit:
Branch: | Stopgaps:
Dependencies: |
-------------------------------------------------+-------------------------
Comment (by wbhart):
Flint doesn't stop you computing a gcd of polynomials over Z/nZ when n is
composite. But the result is probably only mathematically meaningful if no
impossible inverses were encountered (Z/nZ is not an integral domain if n
is composite).
The nmod_poly module does not have any functions to detect impossible
inverses. In fact Flint's invmod will happily return a result even when
there is no inverse modulo n (it is a mathematically meaningful result,
but obviously not an actual inverse, which is impossible). Furthermore,
the gcd function assumes that it really is an inverse, without checking.
This is all done for efficiency reasons. In the case of Z/pZ[x] where p is
prime, you don't want to be wasting a lot of time checking for impossible
inverses.
As there are very few real applications of arithmetic in Z/nZ[x] for
composite n that don't involve large n, we have thus far implemented
functions that detect impossible inverses in the fmpz_mod_poly module,
where the modulus can be any size.
For example, the fmpz_mod_poly_gcd_f function will set one of its
parameters to a factor of n if an impossible inverse is hit. This is
generally what is required in primality testing and factoring algorithms.
In nmod_poly, testing primality of the modulus is cheap and can be done
once when the ring is set up.
Of course, even if no impossible inverses are hit, even for n = p^k for a
prime p, there are still some issues:
* Z/nZ is not an integral domain, which means impossible inverses can be
encountered
* units in Z/nZ[x] are not necessarily of degree 0, e.g. when n = 5^2 we
have (5x+1)*(20x+1) = 1
* as gcd is only defined up to multiplication by a unit, there is no
maximum degree on the gcd of two polynomials in Z/nZ[x]; an implementation
can only hope to return _a_ gcd, and even then it's difficult to
canonicalise (you would have to remove any factors which are units)
* one cannot even guarantee that a gcd would be monic, since the leading
coefficient may not be invertible
In short, gcd over Z/nZ[x] cannot necessarily be computed efficiently nor
is the output necessarily useful.
There are a few options for Sage:
* disallow gcd in Z/nZ[x] unless n is prime
* if n is not prime, use fmpz_mod_poly_gcd_f to compute the gcd and raise
an exception if an impossible inverse is hit
* perhaps it is possible to prove that the output of the gcd in Flint is
correct if it divides both inputs (I'm not sure if this is true or not),
or if some other simple condition holds (n.b: the Euclidean algorithm
would just hang if run with inputs such as those in the example on this
ticket, so clearly Flint does not currently guarantee that it returns the
result of running the Euclidean algorithm unless n is prime)
* it might be possible to use xgcd instead of gcd in the case n is a prime
power and not prime, in combination with a proof that the result is the
gcd if some identity holds (I don't know if this is the case or not)
It is possible that some time in the (distant) future, Flint may offer
nmod_poly_gcd_f. But this is an enormous amount of work to implement. I
don't think it is a priority without a really good application in mind.
--
Ticket URL: <http://trac.sagemath.org/ticket/19611#comment:2>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
