Help understanding whether to implement `fq`, `fq_default` or both

[GiacomoPope]

Next on my list after fmpz_mod_poly is to try and implement finite fields. I see in the 3.0 documentation there are two related types with the *_default options having less methods (I think)

For python-flint should I only focus on fq? What's the use of the default type?

[oscarbenjamin]

The doc for fq_default_ctx_init_type shows what this is for I think:

As per the previous function except that if type == 1 an fq_zech context is created, if type == 2 an fq_nmod and if type == 3 an fq. If type == 0 the functionality is as per the previous function.

For fq_default_ctx_init the doc says:

Initialises the context for prime and extension degree, with name var for the generator. By default, it will try use a Conway polynomial; if one is not available, a random irreducible polynomial will be used.

So the purpose is to provide a generic interface over the three representations fq, fq_nmod and fq_zech. The doc for fq_default_ctx_init does not explicitly say this but the intention is that it will make a good choice for which of the three representations will be used. The code is here:
https://github.com/flintlib/flint2/blob/72ff1553903198ad34830db12d1a8462c52a7e33/src/fq_default/ctx_init_modulus.c#L14

So if you want to construct a context for a finite field of order $q = p^k$ then by default it will use:

• fq_zech if k > 1 and q <= 65536
• fq_nmod if k > 1 and p is word-sized.
• fq if k > 1 and p is not word-sized.
• nmod if k == 1 and p is word-sized.
• fmpz_mod if k == 1 and p is not word-sized.

Then all other fq_default functions are just wrappers that call through to the appropriate routine for the actual type:
https://github.com/flintlib/flint2/blob/72ff1553903198ad34830db12d1a8462c52a7e33/src/fq_default.h#L348-L372

Probably for python-flint it makes most sense to wrap fq_default rather than any of the others. The overhead of the fq_default wrapper is unlikely to be significant compared to the overhead of the Cython wrapper and the Python interpreter.

Any functions that are provided by specific types like fq or fq_nmod could also be obtained in python-flint by performing some conversions.

I suggest to wrap fq_default but to call it fq. Potentially it would be useful to allow specifying the type using fq_default_ctx_init_type so that someone can still effectively choose whether they want to use fq_zech as the internal representation or not. I assume that there are some memory vs speed tradeoffs between fq_zech and fq_nmod.

[oscarbenjamin]

I suggest to wrap fq_default but to call it fq

Or perhaps it should still be called fq_default. So far every python-flint type wraps a Flint C type of the same name which is at least easy to understand for someone who knows what the features of Flint itself are. It might be confusing to change that now, especially to use a name that actually refers to a different type in the C code.

Ultimately a higher-level interface should be made with names that look a bit less like C code but I don't think that we are there yet.

[GiacomoPope]

Thanks Oscar, really appreciate the help. I'll start with fq_default and we'll go from there.