A remark on factorisation

ABSTRACT

We are concerned with factoring polynomials over algebraic extensions of the rationals, and have implemented a variant of Trager's [1976] algorithm, which reduces this problem to that of factoring polynomials over the integers, for which we use Wang's [1978] algorithm (as implemented in REDUCE [Hearn 82] by Moore and Norman [1981]). However, Trager's method often produces a norm polynomial which factors profusely modulo every prime, leading to a combinatorial explosion of trial divisions in Wang's algorithm. We present some simple divisibility tests for polynomials to help combat the cost of this explosion.

REFERENCES

• 1: Anthony C. Hearn, REDUCE - A Case Study in Algebra System Development, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.263-272, April 05-07, 1982
• 2: {Swinnerton-Dyer 69} H. P. F. Swinnerton-Dyer Private communication to E. Berlekamp.
• 3: P. M. A. Moore , A. C. Norman, Implementing a polynomial factorization and GCD package, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.109-116, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806379]
• 4: Barry M. Trager, Algebraic factoring and rational function integration, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.219-226, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806338]
• 5: {Wang 78} P. S. Wang An Improved Polynomial Factoring Algorithm. Math. Comp. vol.32, no.144, (1978), pp1215--1231.