Re: Memory use when factoring big polynomials

[Igor Schein <igor@txc.com>]

On Fri, Oct 30, 1998 at 07:07:37AM -0500, Karim BELABAS wrote:
> 
> I've rewritten this part for version 2.0.12 (due to the initial message
> of
> Igor Schein on this list, complaining about factor(x^120-1) taking
> ages).
> 
> The real culprit is "generic computation" here, which causes millions of
> unnecessary copies and divisions whenever you're working in a finite
> field.
> 2.0.11 (and all previous versions) was completely unable to deal with
> polynomials of degree bigger than, say, 1000 in a satisfactory way.
> You'd
> immediately get a SEGV when trying to factor such a beast over Z for
> instance
> (fixed-size buffers, targeted for degree less than 700...).
> 
> I'll let Igor comment on benches about the situation in version 2.0.12
> if he
> feels like it (he has done a tremendous amount of testing). The 2.0.12
> update
> is long overdue (sorry about that, too much work, too many things
> included).
> I'll try to release it next week.

I must say polynomial factorization has improved dramatically from
2.0.11 to upcoming 2.0.12.  Right now, there're only 2 other packages
( and I've tried them many ) which beat PARI by a factor of several.
When I first noticed the problems with polynomial factorization, PARI
was much worse than all other packages.  Memory consumption, though
also greatly improved, still remains the weak spot.  For practical
purposes, however, it's quite adequate now.  For example, it deals
pretty well with random polynomials.  There's a family of *freak*
cases, which PARI can't handle in reasonable time, however it's
pretty much academic, because one would never have to use them
other than for purely testing purposes, like I did.  

I can provide more information per request, if any1 is interested,
or refer to other sources.

Igor