From: Daniel Lichtblau <danl@wolfram.com>
Newsgroups: sci.math.symbolic
Subject: Re: Benchmark for polynomial factorization
Date: Mon, 26 Oct 1998 13:06:49 -0600

Stefan Wehmeier wrote:
> 
> Igor Schein wrote:
> >
> > Hi, I was wondering if people could try
> > to factor the following polynomial:
> >
> > x^288 + x^285 + x^282 - x^273 - x^270 - x^267 - x^249 - x^246 + x^240
> > + x^237 + x^234 + x^231 - x^225 - x^222 - x^204 - x^201 + x^195 +
> > x^192 + x^189 + x^186 - x^180 - x^177 + x^171 + x^168 + x^165 - x^159
> > - 2*x^156 - x^153 + x^147 + x^144 + x^141 - x^135 - 2*x^132 - x^129 +
> > x^123 + x^120 + x^117 - x^111 - x^108 + x^102 + x^99 + x^96 + x^93 -
> > x^87 - x^84 - x^66 - x^63 + x^57 + x^54 + x^51 + x^48 - x^42 - x^39 -
> > x^21 - x^18 - x^15 + x^6 + x^3 + 1
> >
> > It's a irreducible polynomial ( Phi(585), a cyclotomic
> > polynomial ), so I'm only interested in the timing.
> > I'd like to get a response for as many math packages as possible.
> >
> > Thanks
> > Igor
> 
> A hard example ... I think you will have to wait *days* before you get
> any
> result. (There are usually 24 factors of degree 12 modulo some prime,
> and after lifting,
> 2^{24} subsets of the set of all factors have to be tested. Using the
> LLL algorithm,
> on the other hand, requires lifting to a very high power of the chosen
> prime.) Of course
> you might find some math program that tests for cyclotomic polynomials
> first ...
> 
> Would be interesting to hear about your results.
> 
> Stefan
> 
> --
> Stefan Wehmeier
> stefanw@mupad.de

Possibly you are familiar with this, but most readers are probably
not... There is a nice test described in "A heuristic irreducibility
test for univariate polynomials" by Michael Monagan, J. Symbolic
Computation (1992) 13, 47-57. Any algorithm that interleaves this with
pulling out correct factors, and, in particular, begins with this test,
might quickly deduce that this is irreducible. In Mathematica some
relevant code to this effect might be

In[37]:= tab = Table[{j, PrimeQ[poly /. x->j]}, {j, 25, 50}];

In[38]:= Cases[tab, {_,True}]
Out[38]= {{26, True}}

Actually one can try values as low as 4, if I have read correctly the
result cited above. Monagan also handles cases where there is a fixed
integer divisor that needs to be found and properly accounted for, but
that does not arise in this example.

While this can be a powerful tool for irreducible examples, it is easy
to thwart in a factorization routine. Simply take a pair of polynomials
of this sort, multiply them, then try to factor the result.


Daniel Lichtblau
Wolfram Research