Add support for field extensions

[wchresta]

A lot of Haskell libraries exist for prime fields; there are no good and clean ones for field extensions - the missing construction to fully have a proper finite-field library.

It seems the finite-field library would be a good place to implement field extensions. Does this, in general, make sense for this library?

[msakai]

Yes, I think it makes sense. I haven't implemented field extensions in this finite-field library mainly due to my lack of knowledge in field extensions and computer algebra.

In particular I was wondering following points:

• Implementing field extensions requires implementing several algorithms of polynomials, so that it might be better to make the library into more proper algebra library instead of just finite-field library. (BTW: I have also implemented univariate polynomial factoring (which itself depends on finite-field package) etc. in my toysolver package. Maybe it is better to include this in the same library.)
• Is it possible to define type ExtensionField p k where p and k are type level natural numbers?, or is it better to define ExtensionField p polynomial where polynomial is type level representation of minimal polynomial?
  • For the former type, I was unaware of how to choose minimal polynomial.
  • For the latter type, I was wondering how to represent polynomials in type level. (type level lists + type level natural numbers?)

[wchresta]

These are good questions. As a user of a finite field library, I'm probably mainly interested in things like order, characteristic and generator of the field rather than the concrete representation of the field itself. The representation could (and maybe should) be hidden from the user. A concrete example of this is an implementation difference between Binary Fields and other Fields. Binary field extensions have an especially efficient implementation possibility (represent the coefficients of polynomials over F_2 as bits in a word). There is an article by ekmett about that. I'll think about it some more.

[wchresta]

For arithmetic on polynomials there is polynomial. Maybe we can use that (or steal code from there)

I'm working on a draft for possible types. I'll post them here if I get anywhere.

[msakai]

Thanks!

[wchresta]

Ok, so after some thought, I think the best way forward would be to have a simple Extension type class and type families that go with it extracting the parameters from the type. That way we dont need MultiParamTypeClasses and thus dont clutter the types.