Main thing I'm not so sure about is the new context extension, whether this should be built on top of the fmpz_mod_ctx or instead be a class which takes fmpz_mod_ctx as an argument instead. This second option would allow the creation of fmpz_mod elements by passing the context stored in fmpz_mod_poly_ctx as an arg...

Something like

cdef class fmpx_mod_poly_ctx:
    def __init__(self, mod_ctx):
        self.val = mod_ctx

Then the way of working would be:

F = fmpz_mod_ctx(163)
a = F(3) # fmpz_mod(3, 163)

R = fmpz_mod_poly_ctx(F)
f = R([1,2,3]) # fmpz_mod_poly([1,2,3], 11)

Of course, we could allow either, so we could have:

F = fmpz_mod_ctx(163)
R = fmpz_mod_poly_ctx(F)
assert R == fmpz_mod_poly_ctx(163)

Where when 163 can be cast to fmpz type, we first create the fmpz_mod_ctx and then use this as the value for fmpz_mod_poly_ctx.

If we were working at a higher level I might suggest something like R = ZZ_n(163).poly_ring() or something.

Otherwise I prefer this version:

F = fmpz_mod_ctx(163)
R = fmpz_mod_poly_ctx(F)

The reason I like it is because then R can keep a reference to F and then any method from fmpz_mod_poly that returns fmpz_mod can always ensure to use the exact same context object F. That way any calculation that mixes R and F can also work and it can be fast to check that an element of R matches with an element of F etc in R(2)*F([1,2]).

If we had cached contexts then it wouldn't matter because fmpz_mod_poly_ctx(163) could retrieve F from the cache.

Made the change above about the __getitem__() and also reworked the context. I have also changed __hash__ for mod_ctx and mod_poly_ctx as before it was only the modulus being hashed and I figured these two objects should hash to different values.

I figured these two objects should hash to different values.

It is okay for them to hash to the same value. The hash invariant requires only that equal objects have the same hash. It is not required that unequal objects have different hash so if you want all hashes can just be 1. In practice I doubt that it matters much as I can't imagine someone putting these two objects into a dict/set together at least not in a performance sensitive context.

There's a whole bunch of functions available in flint which might not make it into the first PR for this type, but I might add something like

def berlekamp_massey(self):
    raise NotImplementedError("Function available in Flint but not yet implemeneted in python-flint")

To entice others to work on it if they're interested in having the feature.

So I think I'm missing something about how factor works for Z/NZ.

In flint, I call:

>>> from flint import *
>>> F = fmpz_mod_ctx(163)
>>> R = fmpz_mod_poly_ctx(F)
>>> f = R([1,2,3])
>>> f.factor()
[(x + 115, 1), (x + 103, 1)]

sage: F = GF(163)
sage: R.<x> = PolynomialRing(F)
sage: f = R([1,2,3])
sage: f.factor()
(3) * (x + 103) * (x + 115)

We see that the constant term is missing.

Now, in the fmpz_poly_factor_struct, there's this fmpz_t value which is called c and is the constant term, but for fmpz_mod_poly we have:

    ctypedef struct fmpz_mod_poly_factor_struct:
        fmpz_mod_poly_struct * poly
        slong *exp
        slong num
        slong alloc
    ctypedef fmpz_mod_poly_factor_struct fmpz_mod_poly_factor_t[1]

and there's no storage for this constant term. Is the intention that this is only ever called on monic polynomials?

Another option I guess would be to first collect the leading coefficient with *fmpz_mod_poly_lead to get a pointer to the leading coefficient, then factor the input polynomial (which is treated as a monic polynomial) and then return a tuple (leading_coeff, monic_factors)

Added a few methods to do what I suggest above:

>>> from flint import *
>>> F = fmpz_mod_ctx(163)
>>> R = fmpz_mod_poly_ctx(F)
>>> f = R([1,2,3])
>>> f.leading_coefficient()
fmpz_mod(3, 163)
>>> f.factor()
(fmpz_mod(3, 163), [(x + 115, 1), (x + 103, 1)])
>>> f.monic()
x^2 + 55*x + 109
>>> f.monic().factor()
(fmpz_mod(1, 163), [(x + 115, 1), (x + 103, 1)])

Is the intention that this is only ever called on monic polynomials?

The doc says:

Factorises a non-constant polynomial f into monic irreducible factors

So I guess it always makes the polynomial monic.

The docs don't say if the modulus is assumed to be prime but I imagine that many of the factor related functions would only work for prime modulus in which case the polynomial could always be made monic.

Looks like the modulus should be prime:

In [2]: import flint

In [3]: F = flint.fmpz_mod_ctx(12)
   ...: R1 = flint.fmpz_mod_poly_ctx(F)

In [4]: p = R1([1, 2, 3, 4])

In [5]: p.factor()
Flint exception (Impossible inverse):
    Exception in fmpz_mod_inv: Cannot invert.
Aborted (core dumped)

I guess that failure is from trying to make it monic.

Here it is monic already but the modulue is not prime:

In [1]: import flint

In [2]: F = flint.fmpz_mod_ctx(12)
   ...: R1 = flint.fmpz_mod_poly_ctx(F)

In [3]: p = R1([4, 3, 2, 1])

In [4]: p.factor()
GR_MUST_SUCCEED failure: src/fmpz_mod_poly/gcd.cAborted (core dumped)

What's your opinion on adding a is_prime bool to fmpz_mod_ctx, which is set on initalisation and checked for the cases when the modulus is needed to be prime? We could set this with a check_primality flag, which people can set to off if for some reason they want to include some enormous modulus?

We probably should have prime checking by default if the alternative is a segfault. If it can be done only once per context then I imagine that is fine.

Pushed some more work from last night.

• fmpz_mod_ctz now checks for primality on initialisation, saving us from segfaults
• Many more new methods, with docstrings for most (all)?
• Arithmetic is not tested yet, it's boring and I will do it soon when I am feeling more patient

Added support to get random elements from both fmpz_mod_ctx and fmpz_mod_poly_ctx, other methods and addressed the above issue with __cinit__

Let me know if at some point you would just like to get what is here merged and move on. Not everything needs to be added in one pull request.

I would like anything that is added to be tested though. We should aim for 100% line coverage in this library because it is mostly wrapper code. The bugs are unlikely to be in the detailed algorithms and are mostly just going to be that calling a function with the wrong arguments causes a segfault or something. Knowing that a function here ever succeeds without a segfault is probably enough to have some reasonable confidence that it works for most generic inputs. It is most important just to see that a very simple test passes on each platform rather than checking particularly complicated or difficult inputs.

I'm going to clean up what I have an add a few extra functions and then start working on coverage. I had my wedding yesterday and so have been not-coding, but will get this ready for merging this week :)

• Currently flint returns None when no sqrt is found, I think this should be a ValueError

I don't have a strong preference here.

• There is no integral method for fmpz_mod_poly available from FLINT, so I have to skip this for fmpz_mod_poly

It is easy to add this in Python though:

In [30]: p = flint.fmpq_poly([5, 5, 5, 5, 5])

In [31]: p2 = flint.fmpq_poly([0] + [c/n for n, c in enumerate(p.coeffs(), 1)])

In [32]: p.integral() == p2
Out[32]: True

Ok, made no sqrt be a value error, removed the exact division from _div_ and made it a sep. function, fixed the pow todo and implemented integral pythonically.

Main thing now is get back to 100% coverage and clean up the tests file, and also figure out how to solve the __init__ issue which I have introduced.

Edit:

I also called exact division exact_division, but if you like quoex, we can do this. I don't really mind. More converned about the missing init at the moment :/

More converned about the missing init at the moment :/

That's the thing that concerns me as well. Otherwise I would say let's just merge and continue to improve later but we can't mess around with getting the memory management right: it needs to be correct now and always to the best of our knowledge or otherwise we invite a world of pain in future.

So I've tried something, but I don't know if I like it...

    def __cinit__(self, val, ctx):
        if not typecheck(ctx, fmpz_mod_poly_ctx):
            raise TypeError
        self.ctx = ctx
        fmpz_mod_poly_init(self.val, self.ctx.mod.val)

    def __dealloc__(self):
        fmpz_mod_poly_clear(self.val, self.ctx.mod.val)

    def __init__(self, val, ctx):
        if not typecheck(ctx, fmpz_mod_poly_ctx):
            raise TypeError
        self.ctx = ctx
        check = self.ctx.set_any_as_fmpz_mod_poly(self.val, val)
        if check is NotImplemented:
            raise TypeError 
        self.initialized = True

If we then call

res = fmpz_mod_poly.__new__(fmpz_mod_poly, None, context)

Instead of simply:

res = fmpz_mod_poly.__new__(fmpz_mod_poly)

Then __cinit__() has the ctx it needs to initialise the value. However, I really don't like having to pass None for the value argument when initialising :/

This seems to compile fine though and all the tests pass

So I've tried something, but I don't know if I like it...

If __cinit__ raises TypeError then __dealloc__ will be called and will try to call fmpz_mod_poly_clear without any previous call to fmpz_mod_poly_init.

I think the way that you had the code before was good but just we need to ensure that an fmpz_mod_poly_init function is always used when __new__ is used. It can be like:

def __cinit__(self):
    self.initialized = False

def __dealloc__(self):
    if self.initialized:
        fmpz_mod_poly_clear(self.val, self.ctx.mod.val)

def __init__(self, val, ctx):
    if not typecheck(ctx, fmpz_mod_poly_ctx):
        raise TypeError
    self.ctx = ctx
    fmpz_mod_poly_init(obj.val, ctx)
    self.initialized = True
    check = self.ctx.set_any_as_fmpz_mod_poly(self.val, val)
    if check is NotImplemented:
        raise TypeError

Then when you use __new__ you would do:

obj = fmpz_mod_poly.__new__(fmpz_mod_poly)
fmpz_mod_poly_init(obj.val, ctx)

In other words the code using this becomes responsible for calling the init function if it chooses to use __new__.

The advantage of letting the caller call init is that they can choose which init function to call e.g. in this case there is also fmpz_mod_poly_init2. Since there are only two init functions for fmpz_mod_poly though I would be inclined just to make static methods that handle calling them as well as __new__ so then the caller does:

obj = fmpz_mod_poly.new(ctx) # already initialised
obj = fmpz_mod_poly.new_alloc(ctx, n) # already initalised

Alternatively we can have __cinit__ set this up like:

def __cinit__(self, val, ctx):
    self.initialized = False
    if not typecheck(ctx, fmpz_mod_poly_ctx):
        raise TypeError
    self.ctx = ctx
    fmpz_mod_poly_init(self.val, ctx)
    self.initialized = True

def __dealloc__(self):
    if self.initialized:
        fmpz_mod_poly_clear(self.val, self.ctx)

Which can be used like your version but it handles the initialized/dealloc correctly if __cinit__ does not initialise self.val.

A simpler version without the initialised flag could be:

def __cinit__(self, val, ctx):
    # self.ctx is already set to None here I think
    if not typecheck(ctx, fmpz_mod_poly_ctx):
        raise TypeError
    fmpz_mod_poly_init(self.val, ctx)
    self.ctx = ctx

def __dealloc__(self):
    if self.ctx is not None:
        fmpz_mod_poly_init(self.val, self.ctx)

I think this PR is probably good to go but I need to find time to read through it in detail.

Added a new poly method, which i think makes the code easier to read and recovered 100% coverage.

I think this looks good. I'll merge once CI completes.

Okay looks good. Thanks!