[ANN] Released GaloisFields v1.0

I just released v1.0 of GaloisFields.jl. For those people not familiar – a Galois field (or ‘finite field’) is a finite set that supports addition and multiplication, both with their inverses subtraction and division. The most well-known examples are the integers modulo a prime number p. This package allows using these sets wherever a Number is expected.

Commonly, a bottleneck when using Galois fields is the modulo (mod) operation. An interesting feature of this package is the use of broadcasting to reduce the number of these: whenever there’s a sufficient number of bits in Int, we postpone computing this reduction until the end. Here’s the performance effect:

julia> using GaloisFields
julia> const F = GaloisField(29);
julia> x = rand(F, 1000); y = rand(F, 1000); z = rand(F);
julia> @btime x .+ z .* y; # fused modulo optimization
  2.547 μs (7 allocations: 1.22 KiB)
julia> @btime broadcast((x,z,y) -> x + z * y, x, z, y); # same operation, no special optimization
  4.998 μs (1 allocation: 1.06 KiB)

@b-reinke contributed bug fixes and @Keno contributed support for BitIntegers.jl and code to compute primitive roots of unity. For fields of prime power order, we use Frank Lübeck’s database of Conway polynomials.

10 Likes

How do cast 15 in the GaloisField(7)? It’s should be the identity.

Is there a function to check if an element is a generator in the field?

Thanks for asking!

julia> using GaloisFields
julia> const F = GaloisField(7);
julia> F(15)
1
julia> convert(F, 15)
1

There is, thanks to @Keno:

julia> GaloisFields.is_primitive_root.(F, F.(1:6), char(F) - 1)
6-element BitArray{1}:
 0
 0
 1
 0
 1
 0
1 Like

Hi everyone, Hi @tkluck !
I don’t know if it makes sense to post 2 years after package announcement, but I am trying to use GaloisField with 2^p extension. It seems I have issues with it. Could you provide some help / information? (new to Julia, sorry if my post is not in the appropriate place).

julia> using GaloisFields
julia> const F = GaloisField(2^8)
(𝔽₂₅₆, ##312)

I can see the tuple output which is not the same as without extension. Then when I want to convert, the following issue is output:

julia> F(256)
ERROR: MethodError: objects of type Tuple{DataType, 𝔽₂₅₆} are not callable
Stacktrace:
 [1] top-level scope
   @ REPL[8]:1

And if I use the first tuple element, it acts as GF(2):

julia> a = F[1](15)
1
julia> typeof(a)
𝔽₂₅₆

Thanks for your help!
B.R.

I am sure you found the answer. But to have the answer also in writing here: 15 is equal to 1 in GF(2^8).

Well yes I think I did. In fact I was expecting a behavior like e.g. in matlab where you can name all the elements of GF(2^p) by an integer between 0 and 2^p-1, instead of using a generator element \alpha. I understood that it was not implemented like this.
Thanks for your message however!

@SSF thanks for using GaloisFields.jl . The same question came up on Github before and here’s my answer there: Mapping to/from extension fields · Issue #17 · tkluck/GaloisFields.jl · GitHub

I should probably add methods for reinterpret to do what you’re asking here.

thanks for pointing this Github question and your answer, that’s fine for me!