On Tue, Oct 20, 2020 at 1:40 PM Ralf Hemmecke <[email protected]> wrote: > > 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? :-(
it also takes a fraction of a second in SageMath. Why don't you use an already available fast implementation in C or C++? In this case, SageMath uses NTL https://shoup.net/ntl/ which is very fast, and written by an expert in computational number theory. > 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. -- 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/CAAWYfq3B%2BG%2B4FCYg7WxiqGeWEmiwpJ1YjAjZXq3%2Bt6kDBs9LKQ%40mail.gmail.com.
