Implement fmpz_mod_poly_xgcd for all squarefree modulus?

[user202729]

Currently, fmpz_mod_poly_xgcd only works reliably for prime modulus.

Nevertheless, as long as n is squarefree, then (ℤ/nℤ)[x] ≅ ∏ (ℤ/pℤ)[x] is a principal ideal ring, so xgcd is well-defined — if in the process of performing Euclidean division, a noninvertible nonzero leading coefficient is encountered, use that to factorize n and continue separately for each factor, then crt the result together.

Example: gcd(x, 2) = 3*x+2 in (ℤ/6ℤ)[x]. (x = (3*x+2)*(2*x+3) and 2 = (3*x+2)*4)

Thoughts?

[fredrik-johansson]

Yes, that would be nice, and indeed _fmpz_mod_poly_xgcd_euclidean_f allows returning the divisor.

It would be nice to support returning such a factor in _gr_poly_xgcd_hgcd as well so that the XGCD remains asymptotically fast and so that the same technique can be used more generically. (Though for nmod I guess one could just call n_factor when the xgcd fails...)