What should be the methods of the GaloisField class?

[aspiwack]

Currently, the GaloisField class has a single method: the characteristic (well, and arithmetic, of course).

This is definitely a bit weak, as there are infinite fields with finite characteristic.

So what other methods should there be?

One thing I've seen in the wild, is that people tend to tabulate their Galois field computation. So maybe there should be a method to do that? A witness of the group having finite order, rather than just finite characteristic?

[Multramate]

Yes; it is currently only a skeleton and will be dressed up significantly in the coming weeks. The most obvious additions are the order of the field (possibly the extension degree over the base prime subfield as well), a finite list of elements of the field (possibly as a flattened list, but I'm open to making it something else), and a function denoting the Frobenius automorphism (possibly the p^r-th power Frobenius) - these are already in the list of things to do, as well as other functionalities like exponentiation, square roots, random selection, byte representation, bit operations, pretty printing, discrete logarithms, etc - and the documentation will be updated accordingly. There is also a plan to reorganise the data structures to allow prime fields and extension fields to sit more on an equal footing, so that functions like scalar multiplication can be handled trivially, but this is not a priority. For your last question - could you clarify what the type signature this witness, which would tabulate the field operations, should have?

[aspiwack]

For your last question - could you clarify what the type signature this witness, which would tabulate the field operations, should have?

I have no preconceived idea of what it would look like. But if you have a list of elements, I can use it to generate a table

Map.fromList [ ((x,y), x*y) | x <- elems, y <- elems ]

[aspiwack]

(it's probably better to make two dimensional array, to be honest, but whatever. I'd also typically do it with template haskell so that the table is computed at compile time.)

[Multramate]

Sounds good. We'll see what we can do with the tabulation - and it should hopefully be prettified when all is done.

[Multramate]

Just an update here - there are now a few functions available for the GaloisField class that witnesses its finite order, but the tabulation function hasn't been made - mainly for the reason that polynomials do not have a universally natural ordering (in mathematics at least), and it will be much easier to order them once #8 is settled.

[sdiehl]

This is pretty well-defined now. The interface for galois-field is now:

char  :: k -> Integer
deg   :: k -> Int
order :: k -> Integer
frob  :: k -> k
pow   :: k -> Integer -> k
qnr   :: k
qr    :: k -> Bool
quad  :: k -> k -> k -> Maybe k
rnd   :: MonadRandom m => m k
sr    :: k -> Maybe k