Hello,
The attached file is code comes from the problem of creating the
algebraic closure of PrimeField(p) by dynamically extending with a field
with a new polynomial that does not completely factor. It basically
works, but when I tried with the polynomials over GF(43) I realized very
long running times.
The following maps this to FiniteField(43,84) (the splitting field of
the 3 polynomials
p3 := x^3 - 29
p5 := x^5 - 29
p7 := x^7 - 29
When I factor them on my lapto I get:
Time: 8.57 (EV) + 0.00 (OT) = 8.57 sec
Time: 23.81 (EV) + 0.00 (OT) = 23.82 sec
Time: 35.38 (EV) = 35.38 sec
After analyzing where the time is spent I found that there is an
exptMod(t1, (p1 quo 2)::NNI, fprod) call in ddfact.spad
where t1 and fprod are polynomials of degree 1 and 7 (for the last case)
and (p1 quo 2)::NNI is
81343016389104495051429314429892710283748121052067002779751599748804821941
461709990823638183537929646810274525597886525946443695227097400
Clearly, that is a huge number and the coefficients of the polynomials
are (as elements of FF(43,84)) univariate polynomials of degree 83).
So it is expected to take a while.
However, I did the same computation with Magma in a fraction of a
second. Is FriCAS so bad here? :-(
I guess, we need fast polynomial multiplication here.
Actually, Marc Moreno Maza implemented it.
http://fricas.github.io/api/UnivariatePolynomialMultiplicationPackage
Shouldn't we somehow use it (at least for FiniteField of high degree)?
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/90161cd5-23cf-ebfd-5cb7-a8c0ceff119f%40hemmecke.org.
-- Factorization in FiniteField takes long
)clear complete
A ==> FiniteField(43, 84)
Ax ==> UP('x, A)
x: Ax := monomial(1, 1)$Ax
p3 := x^3 - 29
p5 := x^5 - 29
p7 := x^7 - 29
)set message time on
factor p3
factor p5
factor p7
