Hello Johannes,
as one of the authors of the finite field implementation you might
probably be able to tell me what is happening here, see attachment.
The last
coerce(c2)$F4
takes nearly 18 seconds on my laptop (first time only, of course).
That's probably due to the computation of the discrete logarithm table.
Unfortunately, for p>10^6 that makes the finite field implementation
impractical (at least for my purpose).
Actually, I wonder why it takes so long. Is there really need to trigger
the computation of the table. Doesn't this "coerce" (inclusion of F2
into F4) just mean consider c2 as a constant polynomial in the
representation (SAE) of F4?
Maybe some background for my problem.
In fact, I want to implement algebraic numbers via the following paper.
@article{Steel:AlgebraicallyClosedFields:2010,
author = {Allan K. Steel},
title = {Computing with algebraically closed fields},
journal = {Journal of Symbolic Compuation},
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},
keywords = {Algebraic closure, Algebraic number field, Algebraic
function field, Field extension, Inseparability,
Non-perfect field, Polynomial factorization, Root
finding},
}
As far as I understand, this needs an "evaluation (finite) field" in
which there are enough roots. So potentially, I'd need the algebraic
closure of a prime field of a prime characteristic close to machine
integer size.
Any idea how such a field could be implemented in FriCAS?
I thought, I could somehow use FiniteFieldExtension to dynamically grow
this "evaluation field", but the above problem hinders me in thinking
further in this direction.
Ralf
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/b048ea5e-5885-c8bf-8f71-563c66c563ad%40hemmecke.org.
P ==> PositiveInteger
Z ==> Integer
SI ==> SingleInteger
maxi2 ==> shift(max()$SI, -1)::Z
p := qcoerce(prevPrime(maxi2)$IntegerPrimesPackage(Z))@P
p := nextPrime 1000000
F ==> PrimeField p
f := (x^4+x+1)::UP('x, F)
factor f
F2 ==> FiniteField(p, 2)
ff := factor(f::UP('x, F2))
fl := factorList ff
c2 := coefficient(fl.1.factor, 0)
F4 ==> FiniteFieldExtension(F2, 2)
coerce(c2)$F4
