Implement Finite Field Types and Conversion to SageMath

[GiacomoPope]

Hi!

I've been working on some projects recently where the majority of my work is python, but I'm calling to SageMath to get the polynomial rings of finite fields, which currently uses the NTL bindings.

I'm really interested in instead experimenting with flint, for a variety of reasons, and the two main options I see are:

1. Attempt to further generalise SageMath PolynomialRing to also allow flint implementations by writing new bindings within Sage
2. Work directly with python-flint and try and help cross off some TODO from your README by implementing the bindings for finite field types etc.

Because the SageMath Polynomial Ring classes are wildly out of control, option two feels much more manageable and I was wondering whether the python-flint team would be interested in having these features added.

Also, if I was to start, is anyone else is interested in working on this or is there some partial progress? Are there guidelines I should follow if I was to try and add new features?

[oscarbenjamin]

I was wondering whether the python-flint team would be interested in having these features added.

I am sure that we would, but can you be a bit more explicit about what it is that you would like to add?

I'm not familiar with the references to Sage features so references to Flint features/types/functions are easier (for me) to understand.

Python-flint already has nmod_poly. If I read what you say correctly then it sounds like you are referring to nmod_mpoly. Or should it be fmpz_mod_mpoly?

[oscarbenjamin]

I shouldn't comment so late at night. Looking at this now I see obviously you mean finite fields like fq so for (univariate?) polynomials you probably mean fq_poly, fq_nmod_poly or fq_zech_poly.

Absolutely it would be good to expose those in python-flint but we need to consider exactly what the interface should be. As for multivariate polynomials the question for finite fields is how to represent the context object in python-flint and what the user interface should be for creating the context and then for creating polynomials and matrices over that field.

I also wonder to what extent it makes sense for python-flint's interface to parallel the Flint interface as a low level wrapper or whether it is better to try to develop a more Python-style interface that can smooth over some of the internal details of exactly which representation or algorithm is being used. For example at the C level it clearly makes sense to distinguish between fq and fq_nmod but perhaps in python-flint those could just appear as a single type. I'm not sure whether it also makes sense to abstract over the distinction between fq_zech and fq as well.

[oscarbenjamin]

I discuss the context issue in gh-53 in more general terms. I don't think it is necessary to solve all the problems mentioned there just to get finite fields added in python-flint but the ideas there are worth considering when designing how Flint contexts could be wrapped for finite fields.

[oscarbenjamin]

Also, if I was to start, is anyone else is interested in working on this or is there some partial progress?

I am not aware of anyone working on adding finite fields. I recently met with David Einstein (not sure what his GitHub moniker is) who is working on adding multivariate polynomials like fmpz_mpoly and fmpq_mpoly so if you intend to add multivariate polynomials then there would be some overlap there.

Are there guidelines I should follow if I was to try and add new features?

Um... not really. I guess there could be some discussion about exactly how the contexts should work but otherwise generally following the existing design of python-flint's current types is a good guideline. Tests and documentation should be added.

If you have any questions about how to build python-flint or get a development environment set up then ask here.

[GiacomoPope]

Hey, sorry for being slow to reply over the weekend.

Yes, I was thinking at first just trying to get fq working with fq_poly. While googling around I found: https://github.com/defeo/ffisom/, which seems to write some sage wrappers for flint, so this might be useful, but it's also fairly old so it might just be simpler to start from the beginning.

As for the interface, I think what you suggest is very sensible. For example, we could implement a single FiniteField class, which has local context created on initialisation.

This would store things such as the characteristic, the modulus of the extension (if there is one) etc. Then, if the characteristic is small enough, then functions built from fq_nmod can be picked and fq in the generic case. I'm not familiar with fq_zech so I don't have much to say on this yet. In this sense, a python user wants a FiniteField and then gets for free faster implementations from fq_nmod without worrying about when to pick it. Essentially the python user has a characteristic of type int and shouldn't need to think about word sizes if they dont want.

Then, building a PolynomialRing in my mind makes the most sense if we pass it a field as an argument. For example in sage you can write:

F = FiniteField(163**2, modulus=[1,0,1]) # GF(p^2) with modulus x^2 + 1 = 0
R = PolynomialRing(F, names="X") # Polynomial Ring GF(p^2)[X]

This is quite similar to what you suggest with fZZ.poly([1, 2, 3]) to create a univariate polynomial ring, but you could instead imagine something like

ZZ = fmpz() # initialise some class for the integers
fZZ = ZZ.context() # This would have some context, in the way all these scalars woul

R = PolynomialRing(ZZ) # Here R inherits the context `fZZ` by calling `ZZ.context()` 

Then, if a PolynomialRing class was then made, you can have this as a generic polynomial ring and when you send it the base ring/field (either the integers, or rationals or finite fields).

Then, elements of the polynomial ring fZZ.poly([1, 2, 3]) could be called from R([1,2,3]), and the generator x = R([1]) for the univariate case.

I'll keep thinking about this and also try and read more of the flint documentation, but for the next few weeks I'll be busy either working or on vacation so will make slower than usual progress.

[oscarbenjamin]

Thinking about fq vs fq_nmod the python-flint types would end up having to check which internal type is used in every method. Probably the best way to implement this is to have two Cython classes that share a common base class. Then as much as possible generic code could be in the base class but all calls to Flint's C functions would need to be in the fq or fq_nmod subclasses.

For now though I think that the best thing would be to just forget about fq and implement fq_nmod and fq_nmod_poly in much the same way as nmod and nmod_poly except that a context object would be needed to wrap the Flint context. The simplest thing would be to provide the context object as an additional constructor argument like the modulus for nmod so fq_nmod_poly([1,2,3], ctx).

A higher level interface like GF(163**2).poly([1, 2, 1]) is something that could be added later. For now just exposing the functionality in more or less its raw form is useful like level 1 as discussed here:
#55 (comment)

At that level probably the context object should just have the same name as it does in Flint so it ends up being:

from flint import *

ctx = fq_nmod_ctx(163, 2, "y")
p = fq_nmod_poly([1, 2, 3], ctx)

I think that just exposing Flint's functionality in this relatively raw way is the quickest way to make something usable.

Designing a higher-level interface is something that needs to be thought through more completely. Implementing the higher-level interface is also something that can be done very easily once the lower level pieces are there e.g. if we want fGF(163**2).poly([1, 2, 3]) then actually there is no reason why the fGF object needs to be implemented in C or Cython: it could just be a Python class that calls through to fq_ctx etc under the hood and it could decide whether to use fq or fq_nmod. It is probably easiest to abstract over the C types at the Python level anyway.

[GiacomoPope]

Ahh yes, ok. So for fq we'll need fmpz_mod and fmpz_mod_poly to allow us to build the extensions, so I see why you suggest going for fp_nmod first.

At a selfish level, I need fq_poly as my characteristics are all quite large, but I think getting fq_nmod_poly working is indeed going to be easier as it's one less type to be concerned about.

Edit: cloned the repo and successfully built flint. I guess I'll start looking at fq_nmod first, for the headers, is the plan to just keep growing _flint.pxd by pasting in the appropriate info from https://github.com/flintlib/flint2/blob/trunk/src/fq_nmod.h?

[oscarbenjamin]

I see why you suggest going for fp_nmod first.

Also I imagined that if fq_nmod is the best choice for small characteristics then it would probably be more widely used then fq if both were available (although I might be wrong about that). Either way we would eventually want to add all of these things.

I imagine that you will find that once you have added one type it will be a lot easier to add more. Especially in the cases like fq vs fq_nmod we can probably share most of the code and test code as well.

To add fmpz_mod I would first refactor nmod to extract any generic code that could be reused for fmpz_mod to a superclass so it is sort of like:

class nmod_base:
    ...
    def __add__(self, other):
         # all the tedious coercion etc logic here
         return self._add(other)

class nmod(nmod_base):
     cdef nmod_t val

    cdef _add(nmod self, nmod other):
         # Call the actual C functions here

Then for fmpz_mod you just make a new subclass:

class fmpz_mod(nmod_base):
    cdef fmpz_mod_t val

    cdef _add(fmpz_mod self, fmpz_mod other):
         # Call different C functions

The same approach can be used for all nmod variants. Likewise if the tests are written in the right way then most of them could be shared for the two subclasses. There should be better sharing of things like tests for classes that have commonality like the different _poly classes or different matrix classes etc.

[GiacomoPope]

Yeah I have a heavy bias to large characteristic because I'm often writing proof of concept cryptographic code, but this is certainly niche and the _nmod classes will be more widely used.

Agree re: nmod_base and if I'm writing fp_nmod then it makes sense to first factor this out of the existing code and then the superclasses should all look pretty similar, with the correct C functions called.

[oscarbenjamin]

for the headers, is the plan to just keep growing _flint.pxd

I guess so for now. I discussed scraping the flint headers in gh-54. In general it would be better to refactor some things so feel free to come up with a better design if you want. Don't feel that you need to do that just to get some new types in though.

Also the use of include here causes problems (gh-15):

python-flint/src/flint/pyflint.pyx

Lines 296 to 325 in 99fa557

	include "fmpz.pyx"
	include "fmpz_poly.pyx"
	include "fmpz_mpoly.pyx"
	include "fmpz_mat.pyx"
	include "fmpz_series.pyx"
	include "fmpq.pyx"
	include "fmpq_poly.pyx"
	include "fmpq_mat.pyx"
	include "fmpq_series.pyx"
	include "nmod.pyx"
	include "nmod_poly.pyx"
	include "nmod_mat.pyx"
	include "nmod_series.pyx"
	include "arf.pyx"
	include "arb.pyx"
	include "arb_poly.pyx"
	include "arb_mat.pyx"
	include "arb_series.pyx"
	include "acb.pyx"
	include "acb_poly.pyx"
	include "acb_mat.pyx"
	include "acb_series.pyx"
	include "functions.pyx"
	include "dirichlet.pyx"

Code coverage testing does not work for example (without patching Cython - see bin/coverage.sh).

[GiacomoPope]

Thought this was interesting:

sage: p = random_prime(2**64)
sage: F = GF(p)
sage: a = F.random_element()
sage: b = F.random_element()
sage: 
sage: %timeit a*b
182 ns ± 3.52 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
sage: 
sage: apy, bpy = int(a), int(b)
sage: ppy = int(p)
sage: 
sage: %timeit (apy * bpy) % ppy
181 ns ± 4.27 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
sage: 
sage: from flint import nmod
sage: af = nmod(apy, ppy)
sage: bf = nmod(bpy, ppy)
sage: 
sage: %timeit af * bf
47.2 ns ± 0.723 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

Seems really motivating for me to then keep working on these things for future projects

[oscarbenjamin]

We have finite field scalars and univariate polynomials now after gh-182 and gh-97. These are based on fq_default which abstracts over the different elementary types fq, fq_nmod, fq_zech, etc. I think that is the right choice rather than making separate types for each in python-flint (see gh-91).

Looking at the headers in the flint docs for fq_default there are:

fq_default.h
fq_default_poly.h
fq_default_poly_factor.h
fq_default_mat.h

We have all of these except fq_default_mat now.

There is no fq_default_mpoly although there is fq_nmod_mpoly. I don't know whether it would be worth adding something here in python-flint to make fq_nmod_mpoly available even if it doesn't work for large characteristic and given that hopefully fq_default_mpoly would exist at some point in the future.

An alternative could be to use gr_mpoly for multivariate polynomials although presumably that is slower than fq_nmod_mpoly and it doesn't like like there is e.g. a gr_mpoly_factor that could do what I presume fq_nmod_mpoly_factor can do. Maybe though we could use gr_mpoly but have a few specific operations like factor delegate to specific fq_nmod_mpoly_* functions.

So the situation for finite fields will be a big improvement in python-flint 0.7.0. It would be good to have matrices which could be added fairly easily now if anyone is interested. Perhaps for multivariate polynomials gr should be added first or otherwise an implementation that only wraps fq_nmod_mpoly could be added.

The title of this issue mentions conversions to SageMath. Is that something that still needs doing somehow?

[GiacomoPope]

The title of this issue mentions conversions to SageMath. Is that something that still needs doing somehow?

I think this isn't something we need to do now and is a remnant of my lack of understanding about the project originally.

We have all of these except fq_default_mat now.

I agree this is the obvious next think to add. It should be very very similar to the fmpz_mod_mat class... but I havent had time to look myself yet.

Perhaps for multivariate polynomials gr should be added first or otherwise an implementation that only wraps fq_nmod_mpoly could be added.

I think the gr stuff is probably more useful than the fq_nmod_mpoly, but that's only my own bias. The other thing is the fq_embed stuff, which also has no nice default wrapping yet