Open GiacomoPope opened 1 year ago
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
?
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.
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.
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.
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.
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:
https://github.com/flintlib/python-flint/issues/55#issuecomment-1676478720
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.
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?
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.
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.
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):
https://github.com/flintlib/python-flint/blob/99fa557c8c358cfeec307c6ed11c1315893a9ca9/src/flint/pyflint.pyx#L296-L325
Code coverage testing does not work for example (without patching Cython - see bin/coverage.sh
).
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
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?
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
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:
PolynomialRing
to also allow flint implementations by writing new bindings within Sagepython-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?