Roland Dreier on Thu, 29 Oct 1998 11:25:42 -0600 (CST)


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Memory use when factoring big polynomials


I recently asked gp to factor a polynomial of degree 3425 over F_5, and
even with 40M of memory, gp still ran out of stack space.  The culprit
appears to be very profligate use of memory with polynomial GCDs; even
taking the GCD of two polynomials of this degree can use up all of gp's
memory.

I wouldn't exactly describe this as a bug but I would say that gp needs
improvement here.  For comparison, Shoup's NTL can factor my polynomial in
a few minutes using maybe 4M of memory, so gp could do a lot better.

I got lost looking at ggcd in polarit2.c (admittedly, I didn't spend much
time poking around).  Perhaps someone who understands the code better can
explain where the problem is.

Roland