ffalgclos -- finite field algebraic closure

[Ralf Hemmecke]

My goal is to implement the algebraic closure of Q along the lines of
\cite{Steel:AlgebraicallyClosedFields:2010} (bibtex item below).

Such an implementation seemingly needs the algebraic closure of a finite
field. This is what I present in this mail.

The main idea is that not a true algebraic closure is implemented, but a
domain that is close to it in the following sense.

At each point in time the domain represents a finite extension of the
ground field (that's currently GF(p) in my attached files).
So the factorization works exactly as in a finite field extension.
However, if one uses rootOf(somepoly), then the polynomial is internally
factored and if there is no linear factor, then one of the irreducible
factors is used to extend the current field.
Technically, this means that a new variable is created and the
irreducible polynomial (considered in this new variable) is added to an
internal triangular set. The new variable is then returned as a new root.

So in fact, this domain DynamicAlgebraicClosurePrimeField behaves
like FiniteFieldExtensionByPolynomial, just that instead of one
polynomial, I use a triangular set.

As can be seen from the code, I actually only build on the functions of
PrimeField and some packages, in particular, the factorization in
ddfact.spad, but not on any FiniteFieldExtension* domains.

Luckily, most things I needed were already implemented as category defaults.

However, there is one important change that would have to be done if
DynamicAlgebraicClosurePrimeField should make it into FriCAS. It
concerns ModMonic. Seemingly for efficiency reasons, ModMonic checks in
"setpoly" for certain conditions and then avoids some recomputations.
It took me some time to realize that ModMonic behaves badly for my
dynamic domain. ModMonic(F, SUP F) silently assumes that for finite
fields size()$F is a constant. Well, a reasonable assumption, but bad
for me, since DynamicAlgebraicClosurePrimeField grows in size with each
new root that is not yet in the field. So I had to patch modmon.spad in
a few places. Since these changes are not too costly, I think they can
also be used for the other cases where size()$F is a true constant.

Attached is the code and a small session to demonstrate the things that
I want to work. Maybe there are still some things that do not work
properly, so just take the code as a "work-in-progress".

Comments and bug reports are welcome.

Ralf

@article{Steel:AlgebraicallyClosedFields:2010,
title = {Computing with algebraically closed fields},
journal = JSC,
volume = 45,
number = 3,
pages = {342 - 372},
year = 2010,
issn = {0747-7171},
doi = {10.1016/j.jsc.2009.09.005},
url =
{http://www.sciencedirect.com/science/article/pii/S0747717109001497},
author = {Allan K. Steel},
keywords = {Algebraic closure, Algebraic number field, Algebraic
function field, Field extension, Inseparability,
Non-perfect field, Polynomial factorization, Root
finding},
}