Add a finite field implementation using FLINT's fq and fq_nmod modules

[Jean-Pierre Flori]

Implement finite fields using flint fq and fq_nmod types.

[Jean-Pierre Flori]

I've set up something at u/jpflori/flint_fq. Completely incomplete though.

[Jean-Pierre Flori]

New commits:

​1ba3dbf

First draty implementation of finite fields using FLINT's fq module.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​95106ba	Use fq_inv function.
​b83f88c	Merge remote-tracking branch 'trac/develop' into flint_fq
​fa877df	The fq_div function does not exist in FLINT 2.4 branch.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ae3034c

Make sure that the fq_ctx_t object is initialized when attempting to clean it.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c7990f8

Implement correct polynomial method for FiniteFieldElement_flint_fq.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​986a850	Let build finite field using flint via the GF constructor.
​008a4c3	Homogenize the representation of fq_t element.
​e9bfa58	Fix most tests for now GF flint implem.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4efb03a

Fix comparison for gf flint implem.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​96d5d9d

Fix return value of type for gf flint implem.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​92306ae	Conversion from PARI gen to GF Flint type.
​e5bdf4c	Upgrade to PARI-2.7.1
​ab6bdff	Merge remote-tracking branch 'trac/u/jdemeyer/ticket/15767' into flint_fq
​4b8c871	Fix conversion from pari to Flint implem of GF.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9e9d2ef

Fix for pari conversion of flint implem of GF.

[Jean-Pierre Flori]

Not thouroughly tested but it at least passes its testsuite.

Comments welcome.

[Jean-Pierre Flori]

I've also pushed another branch including an implem using the fq_nmod type at u/jpflori/flint_fq_nmod. Note that you'll need a FLINT version including my latest git commits from ​https://github.com/jpflori/flint2 At least now, FLINT seems to provide implementation faster than PARI for basic arithmetic over all ranges.

Doing the same thing for the fq_zech type should be as easy as for the fq_nmod type. But there is so much code duplication that it should definitely be templated (that should already be done for the fq and fq_nmod types alone). And not sure that the fq_zech type will be so useful as we have Givaro.

[Jean-Pierre Flori]

Still depends on git version of FLINT, my changes are now merged upstream.

---

New commits:

​5d119ab	Merge remote-tracking branch 'trac/develop' into flint_fq
​586fc84	Add GF implem using fq_nmod FLINT type.
​b202170	Only use pxd files for FLINT includes.

[Jean-Pierre Flori]

I'll do the templating stuff in a later tickets. It really needs more thoughts than what I already did here, especially if I want to convert some other implementations to it.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9bc2caf	Initial fix for conversion from pari to flint for ff.
​5eaa6bb	Merge branch 'ticket/16664' into flint_fq

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​24138eb	Move square root functions for finite fields to base class.
​ced21cf	Use correct name for variable in pari implem of ffs.
​80079e4	Fix conversion from flint to pari ffs elements.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​eedb413	Port fixes for flint_fq implem of ffs to flint_fq_nmod implem.
​bc81680	Faster square root for generic finite field implem.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0661730

Produce different (and non-zero...) hashes for FLINT implems of FFs.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​16243d1

Fix comparison for FLINT implems of FFs.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​fe5bce1	Give a little more info in pxd files about flint fq structure.
​de8d00f	Merge remote-tracking branch 'trac/develop' into flint_fq_nmod

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b4fa9ea

Fix for FFs implem using flint fq_nmod module.

[Jeroen Demeyer]

Needs to be merged.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​dfef37b

A little more info for fmpz_poly struct.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ea72beb

Merge remote-tracking branch 'trac/develop' into flint_fq_nmod

[Jean-Pierre Flori]

Should merge cleanly now.

Still needs a git version of FLINT though.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​72dbde0	Merge remote-tracking branch 'trac/develop' into flint_fq_nmod
​fff00d4	Cleanup/reorganization of FLINT imports
​07780b1	Merge remote-tracking branch 'trac/u/jdemeyer/ticket/16428' into flint_fq_nmod
​ce22602	Cleanup/reorganization of FLINT imports
​ef5c338	Merge remote-tracking branch 'trac/u/jdemeyer/ticket/16428' into flint_fq_nmod

[Jeroen Demeyer]

Could you please explicitly list in "Dependencies" the tickets which are merged in this branch? I'm a bit lost in the git forest.

[Jeroen Demeyer]

I don't really like the fact that element_flint_fq_nmod.pyx and element_flint_fq.pyx are almost identical. Wouldn't it make sense to implement a common base class for them or use templating techniques?

[Jeroen Demeyer]

Also, be aware of #16983 and #16855 which could potentially conflict.

[Jean-Pierre Flori]

This is really work in progress, so it's not really ready for review. I thought very hard of templating but it was too much work for the time I had. Note that the pari_ffelt class at least (and maybe the pari_mod one) is also very similar, so the templating/common base class should surely cover a wider area.

I'll fill in the dependencies asap.

[Jeroen Demeyer]

Replying to jpflori:

This is really work in progress, so it's not really ready for review.

Sure, I just wanted to give some comments based on a first glance.

[Jeroen Demeyer]

Replying to jpflori:

Note that the pari_ffelt class at least (and maybe the pari_mod one) is also very similar, so the templating/common base class should surely cover a wider area.

Perhaps. I noticed you moved some functions to element_base.pyx in your branch, could that be made into a separate ticket?

[Jean-Pierre Flori]

Ok, I'll try to do that (because I do agree it would be the good way to go and feel guilty about my dirty commits). There are also some other things related to the PARI FF implem that I'll try to move out of this ticket.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​1607b8f	Merge remote-tracking branch 'origin/develop' into ticket/15015
​7725122	Cosmetic changes
​6957f17	Merge remote-tracking branch 'origin/develop' into ticket/15015
​aca71cb	Upgrade to mpir-2.7.0-alpha12
​67babeb	Fix doctests due to changed xgcd results
​8c7fbbd	Re-enable "not tested" test from #4357
​08fdc35	Merge remote-tracking branch 'trac/u/jdemeyer/ticket/15015' into mpir
​2cd2132	Merge branch 'flint_pxd' into flint_fq_nmod
​ab4e114	Use flint long types.
​3fb1b2c	Avoid conversion from long to integer when building flint ff element.

[Jean-Pierre Flori]

Groumpf, I accidently merged #17148 and #15015 into this one... Not really a problem as we'll probably have to wait for a proper FLINT 2.5 for this one, and that should come after the actual MPIR 2.7.0 release.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6365775

Use FLINT long types for FF classes.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​70df924	Refactor some methods for finite fields elements.
​6ffc64d	Cleanup unused code and move doctests for finite field elements.
​a6649d2	Merge branch 'ticket/17165' into flint_fq_nmod

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c21dbbc	Merge remote-tracking branch 'trac/develop' into flint_fq_nmod
​bb465ee	Proper memory allocation for FLINT FF's modules.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0aed331	Make modular exponentiation of polynomial using FLINT interruptable.
​ef28e27	Better fix for exponentiation of polys using FLINT nmod and test.
​2bf519b	Merge branch 'ticket/17470' into flint_fq_nmod
​55ef7df	Simplify FLINT C types use.

[Jean-Pierre Flori]

I guess the dependencies are correct now.

Apart from bug fixing and heavy testing, the real question is whether I should try to make some code factoring/templating now.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​53db8cc	Merge branch 'ticket/17470' into flint_fq_nmod
​07105b7	Merge remote-tracking branch 'trac/develop' into flint_fq_nmod

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​08d4719	Merge branch 'ticket/17165' into flint_fq_nmod
​dcec4b9	Merge branch 'ticket/17165' into flint_fq_nmod
​44b6b40	Merge remote-tracking branch 'trac/develop' into flint_fq_nmod
​7651317	Merge remote-tracking branch 'trac/u/jpflori/flint_fq_nmod' into flint_fq_nmod

[Jeroen Demeyer]

Like I said before, I still don't like that the fq files are almost identical to the fq_nmod files.

And instead of writing comments like

# JPF: the following should definitely go into element_base.pyx.

just do it (on a different ticket please, same for def rational_reconstruction

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2ef5f6b

Remove rational reconstruction code from FF base class.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a6d7614

Fix _cmp_ and cdefs.pxi for flint FF implem.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​83e7194

Merge branch 'develop' into flint_fq_nmod

[Jean-Pierre Flori]

@Jeroen: where would you put the distutils magic to simplify linking with flint? In only one pxd file in src/sage/libs/flint which is included by all other ones? Or in each of them?

[Jeroen Demeyer]

Replying to jpflori:

@Jeroen: where would you put the distutils magic to simplify linking with flint? In only one pxd file in src/sage/libs/flint which is included by all other ones? Or in each of them?

First of all, I would prefer to move all changes to libs/flint to a different ticket.

If you want distutils magic, I would put it in every .pxd file which defines library functions (in practice, this is probably all of them except types.pxd).

Note #18837 which makes FLINT-related changes to module_list.py. The new ticket should probably depend on #18837.

[Jeroen Demeyer]

Another small comment: you can replace

    ctypedef struct X:
        pass

by

    ctypedef struct X

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d597b9a	Merge remote-tracking branch 'trac/develop' into flint_fq_nmod
​4b08519	Metaclass for inheriting comparison functions
​ac96e64	Merge branch 'develop' into t/18329/ticket/18329
​0e0301a	Fix documentation
​f6058e7	Use sage_getfile instead of inspect.getfile
​54ff301	Merge remote-tracking branch 'trac/u/jdemeyer/ticket/18329' into flint_fq_nmod
​f5e05a4	Remove comparison boilerplate.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ac28f6c	Let FLINT 2.4.5 pretty print fq_nmod elements.
​a62af73	Add FLINT fix for buggy fq_nmod traces.
​822513d	Fix tests for latest Sage dev version.

[Jean-Pierre Flori]

Replying to jdemeyer:

Replying to jpflori:

@Jeroen: where would you put the distutils magic to simplify linking with flint? In only one pxd file in src/sage/libs/flint which is included by all other ones? Or in each of them?

First of all, I would prefer to move all changes to libs/flint to a different ticket.

I only add new files needed by this ticket, I'm not sure it would make sense to add these files in another ticket.

[Jean-Pierre Flori]

Ok, there is also a slight modification to types.h.

[Jean-Pierre Flori]

Replying to jdemeyer:

Another small comment: you can replace

    ctypedef struct X:
        pass

by

    ctypedef struct X

Noted. Note though that the other types in types.h use the syntax with pass. So I'm not sure if we should not modify all of them at once later.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9587ba6

Merge remote-tracking branch 'trac/develop' into flint_fq_nmod

[Jeroen Demeyer]

Replying to jpflori:

I only add new files needed by this ticket, I'm not sure it would make sense to add these files in another ticket.

But you were talking about adding # distutils: libraries = flint, weren't you? I would suggest to do this on a new ticket. So, when you're changing libs/flint anyway, you might as well add the new files too.

[Jean-Pierre Flori]

Replying to jdemeyer:

Replying to jpflori:

I only add new files needed by this ticket, I'm not sure it would make sense to add these files in another ticket.

But you were talking about adding # distutils: libraries = flint, weren't you? I would suggest to do this on a new ticket. So, when you're changing libs/flint anyway, you might as well add the new files too.

Oh yes, the distutils part should definitely be done elsewhere.

[Vincent Delecroix]

Hello,

In _element_constructor_ the following case should not happen

if isinstance(x, self.element_class) and x.parent() is self:

as if parent(x) is self then this is catched by the __call__ of Parent. See line 1080-1083 of parent.pyx

        cdef R = parent_c(x) 
        cdef bint no_extra_args = len(args) == 0 and len(kwds) == 0 
        if R is self and no_extra_args: 
            return x

Instead of making __nonzero__ relies on is_unit I would rather implement __nonzero__ and call it in bot is_unit and is_zero. BTW for the latter this is what is in Element.is_zero by default, so you can even remove it. The reason why is that there is a special slot for __nonzero__ in Python objects. So the fastest (Python) way to do things should be

if not my_element:
    XYZ

and not

if my_element.is_zero():
    XYZ

What are the status of the flint patches? Are there incorporated in flint-2.5? If that is so, it would make sense to first include it into Sage.

Vincent

[Jean-Pierre Flori]

Replying to vdelecroix:

Hello,

In _element_constructor_ the following case should not happen

if isinstance(x, self.element_class) and x.parent() is self:

as if parent(x) is self then this is catched by the __call__ of Parent. See line 1080-1083 of parent.pyx

        cdef R = parent_c(x) 
        cdef bint no_extra_args = len(args) == 0 and len(kwds) == 0 
        if R is self and no_extra_args: 
            return x

Instead of making __nonzero__ relies on is_unit I would rather implement __nonzero__ and call it in bot is_unit and is_zero. BTW for the latter this is what is in Element.is_zero by default, so you can even remove it. The reason why is that there is a special slot for __nonzero__ in Python objects. So the fastest (Python) way to do things should be

if not my_element:
    XYZ

and not

if my_element.is_zero():
    XYZ

Thanks, I'll have a look at both of these. Not that the code is mainly cpoied/pasted from the PARI wrapper by Peter Bruin. I'll also check the PARI wrapper. Note the PARI wrapper is Python rather than Cython (as we have already have a cython "proxy" for PARI elements).

What are the status of the flint patches? Are there incorporated in flint-2.5? If that is so, it would make sense to first include it into Sage.

I guess so. Integrating flint 2.5 first is a good idea anyway. It will also allow to use the lacking in flint 2.4 fq_div function.

Vincent

[Vincent Delecroix]

Replying to jpflori:

Replying to vdelecroix:

What are the status of the flint patches? Are there incorporated in flint-2.5? If that is so, it would make sense to first include it into Sage.

I guess so. Integrating flint 2.5 first is a good idea anyway. It will also allow to use the lacking in flint 2.4 fq_div function.

This is #19009 (needs review).

[Vincent Delecroix]

Conflicts with the flint upgrade (#19009).

[Jeroen Demeyer]

Conflicts with 6.10.beta6. If you fix this conflict, I can easily merge #19646.

[Jean-Pierre Flori]

I guess the branch here is now completely broken. A more current implementation can be found at ​https://github.com/defeo/ffisom/