Slug #837
factor is very slow on some simple input polynomials
Description
The problem lies in CoCoALib, but for simplicity I present it here as CoCoA-5 code.
factor(x^780+780) is very slow; so is factor(x^988+988).
In contrast factor((3*5*7*11*17*x)^988+988) is fairly fast (about 5s);
and factor((7*11*17*19*x)^780+780) is fairly fast (about 9s).
Presumably the problem is that not enough primes are tried; NTL uses a trick where extra primes are tried if the factor search becomes slow. Perhaps do something similar?
History
#1
Updated by John Abbott over 8 years ago
Updated by My "fast" machine in Kassel takes more than 60000s for x^780+780, and 1333s for x^988+988.
In comparison all polys of the form x^n+n for n ranging from 1 to 1000 (but excluding the two slow cases) can be factorized in just 164s on my "fast" machine in Kassel.