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

[jpflori]

Implement finite fields using flint fq and fq_nmod types.

Depends on #19646

CC: @defeo @pjbruin @sagetrac-erousseau

Component: finite rings

Keywords: flint finite field

Author: Jean-Pierre Flori

Branch/Commit: u/jpflori/flint_fq_nmod @ 9587ba6

Issue created by migration from https://trac.sagemath.org/ticket/16664

[jpflori]

comment:1

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

[jpflori]

Commit: 1ba3dbf

[jpflori]

Branch: u/jpflori/flint_fq

[jpflori]

New commits:

1ba3dbf

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

[sagetrac-git]

Changed commit from 1ba3dbf to fa877df

[sagetrac-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.

[sagetrac-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.

[sagetrac-git]

Changed commit from fa877df to ae3034c

[sagetrac-git]

Changed commit from ae3034c to c7990f8

[sagetrac-git]

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

c7990f8

Implement correct polynomial method for FiniteFieldElement_flint_fq.

[sagetrac-git]

Changed commit from c7990f8 to e9bfa58

[sagetrac-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.

[sagetrac-git]

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

4efb03a

Fix comparison for gf flint implem.

[sagetrac-git]

Changed commit from e9bfa58 to 4efb03a

[sagetrac-git]

Changed commit from 4efb03a to 96d5d9d

[sagetrac-git]

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

96d5d9d

Fix return value of type for gf flint implem.

[sagetrac-git]

Changed commit from 96d5d9d to 4b8c871

[sagetrac-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.

[sagetrac-git]

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

9e9d2ef

Fix for pari conversion of flint implem of GF.

[sagetrac-git]

Changed commit from 4b8c871 to 9e9d2ef

[jpflori]

Dependencies: #15767

[jpflori]

comment:12

Not thouroughly tested but it at least passes its testsuite.

Comments welcome.

[jpflori]

Changed work issues from rebasing to none

[sagetrac-git]

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

83e7194

Merge branch 'develop' into flint_fq_nmod

[sagetrac-git]

Changed commit from a6d7614 to 83e7194

[jpflori]

comment:55

@jdemeyer: 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?

[jdemeyer]

comment:56

Replying to @jpflori:

@jdemeyer: 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.

[jdemeyer]

comment:57

Another small comment: you can replace

    ctypedef struct X:
        pass

by

    ctypedef struct X

[sagetrac-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.

[sagetrac-git]

Changed commit from 83e7194 to f5e05a4

[sagetrac-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.

[sagetrac-git]

Changed commit from f5e05a4 to 822513d

[jpflori]

comment:60

Replying to @jdemeyer:

Replying to @jpflori:

@jdemeyer: 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.

[jpflori]

comment:61

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

[jpflori]

comment:62

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.

[sagetrac-git]

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

9587ba6

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

[sagetrac-git]

Changed commit from 822513d to 9587ba6

[jdemeyer]

comment:64

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.

[jpflori]

comment:65

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.

[videlec]

comment:66

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

[jpflori]

comment:67

Replying to @videlec:

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

[videlec]

comment:68

Replying to @jpflori:

Replying to @videlec:

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).

[videlec]

comment:69

Conflicts with the flint upgrade (#19009).

[jdemeyer]

Changed dependencies from #15015, #17470 to #19646

[jdemeyer]

comment:71

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

[jpflori]

comment:73

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