Implement fmpz_mod_poly_div

flintlib / flint

FLINT (Fast Library for Number Theory)

http://www.flintlib.org

GNU Lesser General Public License v3.0

438 stars 243 forks source link

Implement fmpz_mod_poly_div #965

Open wbhart opened 3 years ago

wbhart commented 3 years ago

We have a proper div function in nmod_poly, which depends only on the size of the quotient. We need a similar function for fmpz_mod_poly (which currently depends on the length of the quotient and remainder, as it just calls fmpz_mod_poly_divrem).

wbhart commented 2 years ago

It looks like we need to implement:

[x] fmpz_mod_poly_div_divconquer_recursive
[x] fmpz_mod_poly_div_divconquer
[x] fmpz_mod_poly_div_newton
[x] fmpz_mod_poly_div

I think all the dependencies like mullow are there.

wbhart commented 2 years ago

Note that I also added some tickets for divrem_newton and for making use of div_newton in div. As the crossovers are likely to be huge and should not be profiled until other issues like #1115 are sorted, I will not cover that in this release.

wbhart commented 2 years ago

The only thing that remains now is:

[ ] fmpz_mod_poly_div_f

For a first step, this could just use the same approach as fmpz_mod_poly_divrem_f which just checks invertibility of the leading coeff of B before calling the usual function.