sumiya11
commented
6 days ago Thanks for raising this issue !
Implementing support for finite fields of degree > 1 is possible in principle, and I agree that this would be a nice feature.
So that we are on the same page, I mean support for something like:
using Nemo, Groebner
K, a = finite_field(7, 2, "a");
R, (x,y) = K["x","y"];
groebner([x + a*y]);Implementation-wise, I think Julia generic types simplify our life:
- The F4 in Groebner.jl has generic type of coefficients (i.e. the entries of the F4 matrix can be anything that lives in a field). If we had a type that implements arithmetic in F_q^n, we could plug it in there and F4 should work.
- Then the conversion functions (e.g., the
io_convert_polynomials_to_irthat you have looked at) need to be taught to work correctly with that type.
So, it seems feasible, but indeed would require some work.
I assume that the naming "ir_to" and "to_ir" means converting to and from internal representation?
You are close to the truth :^). Here "ir" stands for intermediate representation. The full pipeline is:
input polynomials -> ir -> internal -> F4 -> internal -> ir -> output polynomials.
(The functions names are io_convert_polynomials_to_ir -> ir_convert_ir_to_internal -> f4! -> ir_convert_internal_to_ir-> io_convert_ir_to_polynomials).
It appears that maybe the internal representation of an element of a GF(p) field is just a UINT. And if that is the case then I suppose to represent an element of a finite field of of degree 3 say would require an array of length 3 of UINTS.
Yes, I think this is one possible approach. Another possibly simpler option is to wrap elements of F_q^n in a struct (say inside of io_convert_polynomials_to_ir), forward field operations to existing implementation (which is say somewhere in Nemo or Oscar), and use this struct in F4:
struct MyFqCoeff
actual_coeff
end
import Base: +, *
+(x::MyFqCoeff, y::MyFqCoeff) = MyFqCoeff(x.actual_coeff + y.actual_coeff)
*(x::MyFqCoeff, y::MyFqCoeff) = MyFqCoeff(x.actual_coeff * y.actual_coeff)
# etc
K, a = finite_field(7, 2, "a");
c1 = MyFqCoeff(K(5))
c1*c1In this case, we need to teach io_convert_polynomials_to_ir and friends to recognize MyFqCoeff.
Furthermore if there are matrices whose entries are coefficients of monomials, which are scalars for degree 1 fields, then that would be quite a bit trickier for coeffients that are m-dimensional vectors.
By the way, Groebner.jl already works with vectors of scalars, though for a different purpose. Here, Coeff defines all supported coefficient types in F4. You can notice that it supports CompositeCoeffZp which is a tuple of several integers.
xyz333math
Currently the only finite fields allowed seem to be the Nemo fields of degree one, for example GF(p) where p is a prime integer; I think that GF is the same as finite_field in Nemo.
I did a quick experiment to find out that function io_convert_polynomials_to_ir(polynomials, options::KeywordArguments) in ./input_output/AbstractAlgebra.jl is the function that checks coeffient types and either allows or disallows the field type. E.g. (suppose p=13), it will allow finite_field(13) but disallow finite_field(13, 3, "a") which are of degree 1 and 3 respectively.
Initially I was going to volunteer to try to code this change myself. But after having looked at the code briefly, I came to the conclusion that it is not at all an easy fix, especially for someone coming in cold, who is not familiar with the code. I cloned the project and played around with the code a bit. It's not obvious what is going on in the functions io_convert_polynomials_to_ir and io_convert_ir_to_polynomials which I believe would be one of the necessary changes to incorporating finite_field of degree > 1. I assume that the naming "_irto" and "_toir" means converting to and from internal representation? It appears that maybe the internal representation of an element of a GF(p) field is just a UINT. And if that is the case then I suppose to represent an element of a finite field of of degree 3 say would require an array of length 3 of UINTS. I.e. elements of finite_field(p, 1) are basically 1-dimensional vectors (i.e. a scalar) and elements of finite_field(p, m) are m-dimensional vectors. Furthermore if there are matrices whose entries are coefficients of monomials, which are scalars for degree 1 fields, then that would be quite a bit trickier for coeffients that are m-dimensional vectors. On the otherhand, for you guys that implemented this package, it goes without saying that it would be much easier for you to add this feature than someone coming in cold. Let me know your thoughts.