An Algorithm On Factorization Of Multivariate Polynomials Over Algebraic Function Field

This paper studies an algorithm for factoring multivariate polynomials over algebraicfunction field. Algorithm is mainly through the evaluation of the parameters and variables toreduce the multivariate polynomial into the univariate polynomial, next make a decomposition tothe univariate polynomial on algebraic extension field, then using Hensel’s lemma to lift thefactors of the polynomial. It presents and demonstrates the method of the construction ofmultivariate Hensel lifting. And it puts forward the multivariate p adiclifting algorithm to liftthe integer coefficients of the polynomials according to the sparse interpolation.First, it introduces the background and significance of the multivariate polynomialfactorization and summarizes some methods to solve this problem. It gives some basic conceptsand the proof of relevant theorems; then it respectively illustrates the problems which areinvolved in the progress of algorithm. In section2part we mainly introduce the relevant basicconcepts of polynomials; according to the problem of the evaluation points, we present theconditions of them, then we respectively give the range of degree bound for the parameters andthe numerical bound in the Section3.In Section4we mainly discuss and prove the multivariateHensel lifting construction theorem, for selecting the zero evaluation points as much as possibleto keep the sparsity of the polynomial, we also give a p adiclifting algorithm which usessparse interpolation; In Section5we introduce the description of algorithm and present anexample to show the main flow of the whole process of the algorithm.