Opened 4 years ago
Last modified 4 years ago
#19611 new defect
Error in gcd for polynomials modulo p^n
Reported by: | roed | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.10 |
Component: | algebra | Keywords: | |
Cc: | jen | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Reported upstream. No feedback yet. | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
We've observed an error in gcds for polynomials over Zmod(5^2)
and Zmod(5^3)
. This seems to be a problem in FLINT's nmod_poly_gcd
, since Sage essentially calls that function directly.
sage: R.<x> = QQ['x'] sage: f1old = x^5 + 7*x^3 + 8*x^2 + 15*x + 19 sage: f1old.is_irreducible() True sage: f2 = f1old.derivative() sage: factor((f1old).discriminant()) 181654981 sage: for i in range(1,5): ....: K.<x> = Zmod(5^i)['x'] #reducing over ZZ/(5^i ZZ) ....: f1 = K(f1old) ....: f2 = f1.derivative() ....: h = gcd(f1,f2) ....: if h.degree() > 0: ....: r = -h.constant_coefficient() ....: print 'over (ZZ/5^%s)[x], gcd is %s, evaluations of f1, f2 at the root are %s, %s'%(i, h, f1(r), f2(r)) over (ZZ/5^2)[x], gcd is x + 1, evaluations of f1, f2 at the root are 4, 0 over (ZZ/5^3)[x], gcd is x + 101, evaluations of f1, f2 at the root are 4, 0
Change History (2)
comment:1 Changed 4 years ago by
- Report Upstream changed from Not yet reported upstream; Will do shortly. to Reported upstream. No feedback yet.
comment:2 Changed 4 years ago by
Note: See
TracTickets for help on using
tickets.
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, since that is impossible). Furthermore, the gcd function assumes that invmod really returns 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 only 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:
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:
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.