Polynomial Factorization Over Algebraic Fields

Factoring polynomials over algebraic extension fields can be traced back to L.Kronecker( Kronecker 1882). A similar algorithm can also be found in V. D. Waerden(Waerden 1953) which was adpoted and improved by B. M. Trager(Trager 1976). Further improvements were given by M. J. Encarnacion(Encarnacion 1997) and M. Nora, K. Yokoyama(Nora and Yokoyama 1997). By using the Chinese remainder theorem, Hensel lemma and Lattice techniques, several different approaches were given in (Wang 1976; Weinberger and Rothschild 1976; Lenstra 1982, 1987; Landau 1985; Abbott 1989).

Our study on algebraic factorization started in 1984, motivated by the need of it in Wu's method(Wu 1984,1987) for geometry theorem proving GTP. Two different methods were proposed in (Hu and Wang 1986) and {Wang 1992, Wu 1994) respectively and applied to GTP (Wang 1994) and irreducible decomposition of algebraic varieties (Wang 1992). We investige along this line and try to work out an optimized algorithm by incorporating and improving different techniques. We focus our attention on factoring multivaritate polynomials over algebraic function fields. The main steps of our algorithm are:

Integer substitution to reduce factorization of a multivariate polyonimial over algebraic function field to that of a univariate polynomial over algebraic number field .

Compute a single extension field from the successive extension field using Wu-Ritt's Characteristic Set method.

Factorize the univariate polyonomial over the single extension field.

Hensel lift the factors as well as the ascending set (that defines the algebraic function field).

Obtain the final factorization using True Factor test.

The two main features of our algorithm are using Characterisitc Set method and Ture Factor test by rational function reconstucting. The algorithm has been implemented in Maple and applied to a set of problems. According to our experiments, it has good overall performance expecially for problems with geometric background.

Bibliography

Abbott
On the factorization of polynomials over algebraic fields.
Ph.D thesis. School of Math. Sci., Univ. of Bath, England (1989).
Corless, R. M., Gianni, P. M. B.M.Trager,B. M and Watt, S. M.
The singular value decomposition for polynomial systems.
In: Proceedings ISSAC '95, Montreal, Canada, July 1995, pp.~195-207.
Encarnacion, M. J.
Factoring polynomial over algebraic number fields via norms.
In: Proceedings ISSAC '97, Hawaii, July 21--23, 1997, ACM Press, New York, pp.~265--270.
Hu, S. and Wang, D.
Fast factorization of polynomials over rational number field or its extension fields.
Kexue Tongbao { bf 31}: 150--156.
Karmarkar,N. and Lakshman, Y. N.
Approximate polynomial greatest common divisors and nearest singular polynomials.
In: Proceedings ISSAC '96, Zurich, Switzerland, July 1996, 35-39.
Kronecker, L.
Grundzuge einer arithmetischen theorie der algebraischen GroBen.
J.f.d.reine u.angew. Math.92, 1-122 (1882).
Landau, S.
Factoring polynomials over algebraic number fields.
SIAM J. Comput. { bf 14} (1985) 184--195.
Lenstra, A. K.
Lattices and factorization of polynomials over algebraic number fields.
In: Proc. EUROCAM '82, Marseille (1982) 32--39.
Lenstra, A. K.
Factoring multivariate polynomials over algebraic number fields.
SIAM J. Comput. { bf 16} (1987) 591--598.
Noro, M. and Yokoyama, K.
Factoring polynomials over algebraic extension fields.
Preprint. FUJITSU.
Trager, B. M.
Algebraic factoring and rational function integration. In: Proceedings SYMSAC '76, Yorktown Heights, August 10--12, 1976, ACM Press, New York, pp.~219--226.
van der Waerden B. L.
Modern Algebra.
vol. 1. Engl. transl. by Blum. New York:Frederick Vngar Publ. co. 1953.
Wang, D.
A method for factorizing multivariate polynomials over successive algebraic extension fields.
Preprint. RISC Linz.
Wang, D.
Algebraic factoring and geometry theorem proving.
In: Proceedings CADE-12, Nancy, June 28 -- July 1, 1994, Springer, Berlin Heidelberg New York Tokyo, pp.386--400 (Lecture notes in artificial intelligence, vol. 814).
Wang, D.
An implementation of the characteristic set method in Maple.
In: Pfalzgraf, J., Wang, D. (eds.): Automated practical reasoning: Algebraic approaches. Springer, Wien New York, pp.187--201.
D.M.Wang and L.H.Zhi
Algebraic Factorization Applied to Geometric Problems
Proceedings of the Asian Symposium on Computer Mathematics, pp.23-36, Lan Zhou, China, Auguest 6-8, 1998.
Wang, P. S.
Factoring multivariate polynomials over algebraic number fields.
Math. Comput. 30 (1976) 324--336.
Weinberger, P. J. and Rothschild, L. P.
Factoring polynomials over algebraic number fields.
ACM Trans. Math. Softw.2 (1976) 335--350.
Wu, W.T
Basic principles of mechanical theorem proving in elementary geometries.
J. Syst. Sci. Math. Sci. 4: 207--235 [also in J. Automat. Reason. 2 : 221--252 (1986)].
Wu, W.T
A zero structure theorem for polynomial equations-solving.
Math. Mech. Res.Preprints : 2--12.
Wu, W.T
Some remarks on factorization and GCD of multivariate polynomials.
Math Mech Res Preprints 3: 1--14.
Zassenhaus
On Hensel factorization I.
J. Number Theory 1(1969) 291--311.
L.H.Zhi
Polynomial factorization over algebraic fields and its applications.
Ph.D thesis, Academia Sinica, China (1996)
L.H.Zhi
An Optimal Method for Algebraic Factoring
Journal of Computer Science and Technology, pp 1-8, January 1997.

Return to Zhi's Home