On Fri, Jul 14, 2023 at 02:57:16AM +0200, Waldek Hebisch wrote:
> On Thu, Jul 13, 2023 at 09:00:29AM +0200, Ralf Hemmecke wrote:
> >
> > Code is currently here. I haven't touched it recently, but it worked for
> > simple cases, became, however, unmanageably slow with several extensions
> > due to slow factorization of finite fields in FriCAS.
> >
> > https://github.com/hemmecke/qeta/blob/master/src/iffts.spad
> > https://github.com/hemmecke/qeta/blob/master/src/ffalgclos.spad
> > https://github.com/hemmecke/qeta/blob/master/src/algclos.spad
>
> Concerning slow factorization: one significant reason for slow
> factorization is that operations in general finite fields are
> slow. And AFAICS finite fields represented by triangular sets
> are slower than other slow variants.
>
> Another thing is that you use expensive operations when faster
> alternatives would do. For example, factoring
>
> x^17 - 11*13*17*19
>
> over FiniteField(16777777,17) takes 22.89 sec, factoring over
> FiniteField(2305843009213693921,17) take 150.71, finding
> root by powering can be done probably in few milliseconds.
I have now commited code that switches univariate factorization
over finite fields to new factorizer. Now the same polynomial
over FiniteField(16777777,17) takes 6.48, over
FiniteField(2305843009213693921,17) takes 35.22.
Improvement is mostly due to better algorithm, for those fields
both old and new factorizer use generic arithmetic in finite fields.
Improvement is possible from faster arithmetic routines. But
large prime like 2305843009213693921 is more expensive than
smaller primes. Currently probably best approach would handle
2305843009213693921 via multimodular method. It needs about
5 machine-handled moduli so rough estimate is that it is going
to be about 5-8 time slower.
--
Waldek Hebisch
--
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/ZLMh0Cb4cteIKMFV%40fricas.math.uni.wroc.pl.
