From: zimmerma@leibniz.loria.fr (Paul Zimmermann)
Newsgroups: sci.math.symbolic
Subject: von zur Gathen challenge
Date: 06 Nov 1995 13:19:43 GMT
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
}
--
Paul Zimmermann
INRIA Lorraine
Technopole de Nancy-Brabois
615 rue du Jardin Botanique
BP 101
F-54600 Villers-les-Nancy
Paul.Zimmermann@loria.fr