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