Use exact division for a/b for fmpz, fmpz_mat, and *_poly

[oscarbenjamin]

Use exact division for fmpz etc e.g.:

In [3]: fmpz(4)/fmpz(2)
Out[3]: 2

In [4]: fmpz(4)/fmpz(3)
---------------------------------------------------------------------------
DomainError

Prevously fmpz_mat and fmpz_poly when divided by fmpz would give convert to fmpq but now only exact division is supported:

In [5]: fmpz_poly([2, 4])
Out[5]: 4*x + 2

In [6]: fmpz_poly([2, 4]) / 2
Out[6]: 2*x + 1

In [7]: fmpz_poly([2, 4]) / 3
---------------------------------------------------------------------------
DomainError

Also add exact division for fmpz_poly, fmpq_poly, nmod_poly and fmpz_mod_poly:

In [12]: fmpz_poly([2, 4]) / fmpz_poly([1, 2])
Out[12]: 2

In [13]: fmpz_poly([2, 4]) / fmpz_poly([1, 3])
---------------------------------------------------------------------------
DomainError

This is all working as far as I can tell apart from the case of nmod_poly and fmpz_mod_poly with non-prime moduli e.g.:

In [15]: nmod_poly([2, 3], 10) / 2
Flint exception (Impossible inverse):
    Cannot invert modulo 2*5
Aborted (core dumped)

The same core dump is seen with divmod (an existing problem, not changed in this PR):

divmod(nmod_poly([2, 3], 10), 2)
Flint exception (Impossible inverse):
    Cannot invert modulo 2*5
Aborted (core dumped)

[oscarbenjamin]

There is a bug in the fmpz_mod_poly.exact_division method on master (not caused by this PR) when the modulus is composite:

In [1]: from flint import *

In [2]:     F_cmp = fmpz_mod_ctx(10)
   ...:     R_cmp = fmpz_mod_poly_ctx(F_cmp)
   ...:     f_cmp = R_cmp([1,2,3,4,5])
   ...:     f_bad = R_cmp([2,2,2,2,2])

In [3]: f_cmp.exact_division(R_cmp([2]))
Out[3]: 0

The code is here:

python-flint/src/flint/types/fmpz_mod_poly.pyx

Lines 457 to 489 in ea65d5f

	def exact_division(self, right):
	"""
	Attempt to compute the exact quotient of self with other
	Raises a value error if divison without remainer is not
	possible.
	>>> R = fmpz_mod_poly_ctx(163)
	>>> f = R([1,2,1])
	>>> g = R([1,1])
	>>> f.exact_division(g)
	x + 1
	"""
	cdef bint check
	cdef fmpz_mod_poly res
	# Case when right is not fmpz_mod_poly, try to convert to fmpz
	right = self.ctx.any_as_fmpz_mod_poly(right)
	if right is NotImplemented:
	raise TypeError(f"Cannot convert {right} to `fmpz_mod_poly` type.")
	if right == 0:
	raise ZeroDivisionError(f"Cannot divide by zero")
	res = self.ctx.new_ctype_poly()
	check = fmpz_mod_poly_divides(
	res.val, self.val, (<fmpz_mod_poly>right).val, res.ctx.mod.val
	)
	if check == 0:
	raise ValueError(
	f"{right} does not divide {self}"
	)
	return res

As far as I can tell everything works up to the call to fmpz_mod_poly_divides which returns 1 (meaning divisible) but sets the quotient to zero.

Maybe fmpz_mod_poly_divides should not be used with non-prime moduli although that is not documented. It is not clear to me if there is an alternative that could be used. I'm not sure how much to worry about the case of non-prime moduli in general. I don't personally have any use for it and it only seems to have only patchy support in Flint.

Maybe just anything related to any kind of division should be disallowed in python-flint for non-prime characteristic. Otherwise it seems like there will always be cases where python-flint calls some function that is not guaranteed to return sensible results or might abort on some inputs.

Checking if the modulus is prime can be done when creating the context so it does not need to slow down basic operations.

[oscarbenjamin]

I think that non-prime moduli can be dealt with later. There would need to be a context object for nmod so that it can keep track of whether or not the modulus is prime.

For now this gets the right behaviour in the well-defined cases so let's get it in.