I am happy to announce the factorization using MuPAD 1.2.2 of the polynomial x^500+x+1 mod p_500 where p_500=nextprime(PI*2^500)= 1028365988609634673326338415150375686163476496911358755019401491408784320856 3500712840304045958917565049748851786214229816233622223046670298426214405541. This polynomial is part of the ``von zur Gathen Factorization Challenge'' [vonzurGathen92], which is a list of polynomials with ``most wanted factorizations'' proposed by Joachim von zur Gathen, in order to ``tell us where the boundaries of `routine' and `special effort' factorization are, and which methods achieve the extremes.''
The factorization was done with MuPAD 1.2.2 on a Sun Sparc-10 at 72 Mhz, installed at the Medicis computing center at Ecole Polytechnique (France). It took 226896 seconds of cpu time, i.e. about 63 hours. To my knowledge, this is the current record for the von zur Gathen challenge using a general computer algebra system. The previous record was hold by Magma [BoCaPlSt94] (degree 300 in 110 hours on a 28.5 MIP SunMP670 in 1994) and before by Maple [Monagan93] (degree 200 in 30 hours on a DEC 3100 in 1993). MuPAD implements Shoup's algorithm [Shoup94].
The MuPAD input was the following:
>> DIGITS:=200: N:=500: >> p:=nextprime(ceil(PI*2^N)): >> f:=poly(x^N+x+1,IntMod(p)): >> factor(f);This polynomial has 9 factors, including three linear factors, one factor of degree 12, one of degree 15, one of degree 17, one of degree 20, one of degree 68 and one big factor of degree 365. The factorization can be obtained on http://www.loria.fr/~zimmerma/mupad.
I have checked the factorization using Maple. Checking that the product of the given factors is x^500+x+1 was easy. To check that each factor was irreducible, I used the function Berlekamp of Maple, which implements Berlekamp's algorithm. It took about 13 days to check that the largest factor of degree 365 was irreducible.
@Misc{BoCaPlSt94,
author = "W. Bosma and J. Cannon and C. Playoust and A. Steel",
title = "Solving problems with {M}agma",
year = 1994,
note = "preprint"
}
@article{Monagan93,
author = "Michael B. Monagan",
title = "von zur Gathen's Factorization Challenge",
journal = "SIGSAM Bulletin",
volume = 27,
number = 2,
year = 1993,
pages = "13--18",
month = apr
}
@misc{Shoup94,
author = "Victor Shoup",
title = "A New Polynomial Factorization Algorithm and its Implementation",
year = 1994,
month = aug,
note = "46 pages"
}
@article{vonzurGathen92,
author = "von zur Gathen",
title = "A Polynomial Factorization Challenge",
journal = "SIGSAM Bulletin",
year = 1992,
volume = 26,
number = 2,
pages = "22--24",
month = apr
}