Version française

• A Maple to MuPAD translator by François Thomasset.
• Fonctionnalités générales de MuPAD et différences par rapport à Maple

• example of a dynamic module in MuPAD, with the 'magnum' factorization program

## Polynomial Factorization Challenges: a collection of polynomials difficult to factor

• Here are some big polynomials to test factorization over Z in your favorite CAS. The polynomial P1(x) has degree 156, coefficients up to 424 digits, and 36 factors (12 of degree 2, 15 of degree 4, 9 of degree 8). The polynomial P2(x) has degree 196, coefficients up to 419 digits and 12 factors (2 of degree 2, 4 of degree 12 and 6 of degree 24). The polynomial P3(x) has degree 336, coefficients up to 597 digits and 16 factors (4 of degree 12 and 12 of degree 24). The polynomial P4(x), has degree 462, coefficients up to 756 digits, and two factors of degree 66 and 396. The polynomial P5(x) has degree 64, coefficients up to 40 digits and is irreductible. The polynomial P6(x) has degree 144, coefficients up to 165 digits and has 4 factors of degree 12 and 2 factors of degree 48. The polynomial P7(x) has degree 384 and coefficients up to 57 digits. Using a new algorithm based on the knapsack problem, Mark van Hoeij proved that P7 is irreducible in about 8000 seconds. The polynomial P8(x9) has degree 972 and coefficients up to 213 digits. Victor Shoup proved on March 28 that P8 is irreducible.
Where they come from. P1 comes from the Rational Univariate Representation (RUR) of the Cyclic 6 system, P2 and P3 come from the RUR of Cyclic 7. P4 was contributed by A. Hulpke and H. Matzat: it is the 5-set resolvent of the polynomial f = x^11 + 101*x^10 + 4151*x^9 + 87851*x^8 + 976826*x^7 + 4621826*x^6 - 5948674*x^5 - 113111674*x^4 - 12236299*x^3 + 1119536201*x^2 - 1660753125*x - 332150625 and its factorization would prove that f has Galois group M11. P5 is the Swinnerton-Dyer polynomial for 2,3,5,7,11,13, i.e. the product of all terms of the form x+/-sqrt(2)+/-...+/-sqrt(13). It is a "bad" polynomial for the method of factoring in Fp and combining the factors in Z, because all its factors in Fp are of degree at most 2. P6 is the resultant with respect to x of the polynomial p = -2566974800*x^2 +134697056*x^4 -3312297*x^6 +43109*x^8 -308*x^10 +x^12 +1142440000 with p(y-2*x); it was contributed by Frederic Lehobey and Nicolas Rennert. P7 (contributed by John Abbott) is the norm of x^6 + (a1+a2+a3+a4+a5+a6)*(x^4-x^2) + 1 with a6^2-2, a5^2-3, a4^2-5, a3^2-7, a2^2-11 and a1^2-13, i.e. the resultant of that polynomial with a6^2-2 with respect to a6, then with a5^2-3 wrt a5, and so on. P8 (contributed by Jean-Charles Faugere) comes from the Groebner basis of Cyclic 9.
Timings. Here are some timings on cosimo.medicis.polytechnique.fr, a 500Mhz Compaq DS20E (processor EV6 i.e. Alpha 21264) with 4096MB of main memory (column Knapsack shows timings obtained with Mark van Hoeij Maple implementation of his knapsack algorithm, see comments here):
 polynomial degree height Maple V.5.1 NTL 4.3 Math 3.0.2 Magma V2.6-2 Knapsack P1 156 424 0.6s 0.3s 163s 2.4s 1.0s P2 196 419 1.8s 1.0s 164s 5.1s 5.0s P3 336 597 2.4s 2.0s 42s 5.8s P4 462 756 >50000s 15s 1539s P5 64 40 >50000s 0.4s 27.1s P6 144 165 48s 0.7s 12.6s P7 384 57 8.7s 706.8s P8 972 213 >50000s 30s 1868s
On a 133MHz Pentium with 12MB of memory and GAP-3.5 (current development version), Alexander Hulpke (Alexander.Hulpke@math.rwth-Aachen.de) factored P1 in 26 minutes, P2 in 8 minutes and P3 in 43 minutes. On a SparcStation 4 with a factorization code which will be included in CoCoA, John Abbott factored P1 in 12s, P2 in 13s and P3 in 45s.

• Here is a degree 35 polynomial with 172 terms over F_5[x,y,z] to factor (from MUG, Nivaldo Nunes de Medeiros Junior , January 1996). John Abbott managed to factor it using Axiom in July 2000 on a 200MHz Pentium in about 145000 seconds. Magma V2.6-2 factors it in 0.3 second on a PII-400 under Linux.

• The factor degrees of the polynomials f[n]=x^n+x+1 modulo p[n]=nextprime(PI*2^n) for 1<=n<=500. and of the Shoup's polynomials. These factorizations were done with MuPAD 1.2.2 on different workstations in November, December 1995, January and February 1996.
• The factorization of the polynomial x^500+x+1 modulo the 500-bit prime number nextprime(PI*2^500). This factorization was obtained using MuPAD 1.2.2 in two and a half days on a Sun Sparc-10 of the Medicis center at Ecole Polytechnique (France). This polynomial has 9 factors, of degrees 1, 1, 1, 12, 15, 17, 20, 68 and 365 respectively. The file contains a list l of 19 elements such that l[2], l[4], l[6], ..., l[18] are the factors.