Error in gcd for polynomials modulo p^n

[roed314]

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

Upstream: Reported upstream. No feedback yet.

CC: @jbalakrishnan

Component: algebra

Issue created by migration from https://trac.sagemath.org/ticket/19611

[roed314]

Changed upstream from Not yet reported upstream; Will do shortly. to Reported upstream. No feedback yet.

[wbhart]

comment:2

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:

• 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² we have (5x+1)*(20x+1) = 1

• as gcd is only at best 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 for starters).

• 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)

• implement some other algorithm, guaranteed to return a gcd

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.