search

oscar-system / Oscar.jl

A comprehensive open source computer algebra system for computations in algebra, geometry, and number theory.
https://www.oscar-system.org
Other
338 stars 120 forks source link

Too many finite fields (which to support? what constructors to use? dealing with differences in behaviour)) #867

Closed fingolfin closed 5 months ago

fingolfin commented 2 years ago

As @fieker requested it I was trying to add some more conversion methods between GAP finite field (elements) and their OSCAR counterparts. I looked at the following seven (or eight, depending on how you count) finite field implementations in OSCAR (I am deliberately ignoring those from Singular.jl):

julia> subtypes(FinField)
7-element Vector{Any}:
 AbstractAlgebra.GFField
 FqDefaultFiniteField
 FqFiniteField
 FqNmodFiniteField
 Hecke.RelFinField
 Nemo.GaloisField
 Nemo.GaloisFmpzField

1: which of these types "should" I support / should we support generically?

As in, any place someone using OSCAR may pass in a finite field element, that type at least is supported? And conversely, if producing a finite field element, that type is returned?

Probably at the very least that should be the types that are produced by GF and FiniteField. Which according to my tests are:

I guess it's fair to ignore AbstractAlgebra.GFField. But what about FqDefaultFiniteField -- perhaps that'll become our savior one day and replace the four types listed above by default?

2: Given an integer, how to obtain the "corresponding" finite field element (FFE)? How to do so "generically" and "efficiently"?

[ Actually, I had serious trouble with this... but after restarting Oscar, some code that reproducibly did not work before suddenly started to work... very strange. Anyway, I list the following purely for completeness)

I wanted to experiment with this. To keep things simple, I decided to start with just prime fields, being the "easiest" case. So I tried to instantiate them all to represent GF(5). I realize there are dedicated functions for most of these, but that's not the point here.

julia> function make_RelFinField_prime(p) # hack to get Hecke.RelFinField prime field
           F, gF = FiniteField(p, 2, cached = false)
           x = PolynomialRing(F, "x", cached = false)[2]
           f = x^2 + gF*x + 1
           @assert is_irreducible(f)
           K, gK = FiniteField(f, "a")
           return K
       end;

julia> f5s = [
       AbstractAlgebra.GFField{Int}(5)
       AbstractAlgebra.GFField{BigInt}(big(5))
       FqDefaultFiniteField(fmpz(5), 1, :x)
       FqFiniteField(fmpz(5), 1, :x)
       FqNmodFiniteField(fmpz(5), 1, :x)
       make_RelFinField_prime(5)
       Nemo.GaloisField(UInt(5))
       Nemo.GaloisFmpzField(fmpz(5))
       ]
8-element Vector{FinField}:
 Finite field F_5
 Finite field F_5
 Finite field of degree 1 over F_5
 Finite field of degree 1 over F_5
 Finite field of degree 1 over F_5
 Field extension defined by x + 1 over Finite field of degree 1 over F_5
 Galois field with characteristic 5
 Galois field with characteristic 5

Now how do I get e.g. 3 + 5Z... Well, just do F(3) (actually, in a previous version of this text, I reported various issues where this did not work, but after restarting Oscar, all is fine. Odd)

julia> [ try F(3) catch end  for F in f5s ]
8-element Vector{FinFieldElem}:
 3
 3
 3
 3
 3
 3
 3
 3

3. How to lift elements from GF(p) to the integers?

I was expecting lift to be the answer, but again that only worked for 50% of the test fields:

julia> [ try typeof(lift(one(F))) catch end  for F in f5s ]
8-element Vector{Union{Nothing, DataType}}:
 BigInt
 BigInt
 nothing
 nothing
 nothing
 nothing
 fmpz
 fmpz

Perhaps this is because several of these are types which support extensions of degree > 1 and just because I specified degree 1 doesn't mean they support such a "naive" lift. Looking at some type signatures, it seems lift allows for a polynomial ring as extra argument (usually as the first, but sometimes the second?!). Trying that:

julia> R,t = ZZ[:t]; [ try typeof(lift(R, one(F))) catch end  for F in f5s ]
8-element Vector{Union{Nothing, DataType}}:
 nothing
 nothing
 fmpz_poly
 nothing
 nothing
 nothing
 nothing
 nothing

Hmmm...

julia> R,t = GF(5)[:t]; [ try typeof(lift(R, one(F))) catch end  for F in f5s ]
8-element Vector{Union{Nothing, DataType}}:
 nothing
 nothing
 nothing
 nothing
 gfp_poly
 nothing
 nothing
 nothing

Next I tried the same but with GF(fmpz(5))[:t] which lead to a segfault in Julia 1.6.4 on my intel Mac (I wasn't able to reproduce it, though, and so later I discovered that there are zero cases where this produces something useful).

There doesn't seem to be any lift method for Hecke.RelFinFieldElem. The one other lift method I did not yet hit upon in the above examples is lift(R::GFPFmpzPolyRing, x::fq), where I just couldn't be bothered to figure out how to construct a GFPFmpzPolyRing.

WISHLIST: Provide a uniform way to obtain this kind of lift form a finite field.

fingolfin commented 2 years ago

@fieker asked what I think lift should do when given a non-prime-field element: I was thinking that if that element lives in the prime field, return an integer, otherwise an error. But I am also fine with it always returning an error. But in the end, I'd like a way to generically access finite field elements somehow. Right now, I guess I'll have to follow what Giovanni did in src/Groups/matrices/iso_oscar_gap and implement separate methods for each of the finite field types (or perhaps not "each", I can probably handle a few at a time shrug). I'll update this once I got farther with in the non-primefield case

tthsqe12 commented 2 years ago

A uniform way to ift from any finite field to ZZ or ZZ[x]? Sounds a bit restrictive on the finite field ... for example, what is this supposed to do for the relative extensions as above? Note, the following already exist, and I find it perfectly reasonable that when modulus(finite field) can be lifted to ZZ[x], then the elements should be able to be lifted as well. Though, generically, finite fields implement no modulus and base_ring is undefined.

julia> F, a = FiniteField(fmpz(11), 5, "a")
(Finite field of degree 5 over F_11, a)

julia> m = modulus(F)    # this is supposed to be irreducible :)
T^5 + 10*T^2 + 9

julia> R = parent(m)
Univariate Polynomial Ring in T over Galois field with characteristic 11

julia> lift(R, a^6)
T^3 + 2*T

julia> lift(ZZ["x"][1], ans)
x^3 + 2*x

Note this also works the same way without the fmpz.

fieker commented 2 years ago

To me, generically, if this is what you want, then the finite field is a residue field. If it is constructed as such, it should also come with the projection map which allows a pre-image. Otherwise: since not all Z[x] are identical, what parent should be chosen?

On Mon, Dec 06, 2021 at 03:10:34AM -0800, dan wrote:

A uniform way to ift from any finite field to ZZ or ZZ[x]? Sounds a bit restrictive on the finite field ... for example, what is this supposed to do for the relative extensions as above? Note, the following already exist, and I find it perfectly reasonable that when modulus(finite field) can be lifted to ZZ[x], then the elements should be able to be lifted as well. Though, generically, finite fields implement no modulus and base_ring is undefined.

julia> F, a = FiniteField(fmpz(11), 5, "a")
(Finite field of degree 5 over F_11, a)

julia> m = modulus(F)    # this is supposed to be irreducible :)
T^5 + 10*T^2 + 9

julia> R = parent(m)
Univariate Polynomial Ring in T over Galois field with characteristic 11

julia> lift(R, a^6)
T^3 + 2*T

julia> lift(ZZ["x"][1], ans)
x^3 + 2*x

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/oscar-system/Oscar.jl/issues/867#issuecomment-986674421

tthsqe12 commented 2 years ago

@fingolfin Would you like a lift directly from some finite field to ZZ[x] so that you can do lift(ZZ["x"][1], a^6)?

fingolfin commented 5 months ago

I think this has been resolved by @thofma via the new "unified" finite field type.