连续代数扩域上多项式因式分解的Trager算法

多项式的因式分解是符号计算中最基本的算法,二十世纪六十年代开始出现的关于多项式因式分解的工作被认为是符号计算领域的起源．目前多项式的因式分解已经成熟,并已在Maple等符号计算软件中实现,但代数扩域上的因式分解算法还有待进一步改进．代数扩域上的基本算法是Trager算法．Weinberger等提出了基于Hensel提升的算法．这些算法是在单个扩域上做因式分解．而在吴零点分解定理中,多个代数扩域上的因式分解是非常基本的一步,主要用于不可约升列的计算．为了解决这一问题,吴文俊,胡森、王东明分别提出了基于方程求解的多个扩域上的因式分解算法．王东明、林东岱提出了另外一个算法Trager算法相似,将问题化为有理数域上的分解．他们应用了吴的三角化算法,因此算法的终止性依赖于吴方法的计算．支丽红则将提升技巧用于多个扩域上的因式分解算法．本文将Trager的算法直接推广为连续扩域上的因式分解,只涉及结式计算与有理数域上的因式分解,给出了多个代数扩域上的因式分解一个直接的算法．

Trager's Factorization Algorithm over Successive Extension Fields

Polynomial factorizations are basic problems in symbolic computation.Poly- nomial factorization algorithms appeared in the 1960's are considered to be the origin of the field of symbolic computation.At present,polynomial factorization algorithms are well estab- lished and implemented in symbolic computation software such as MAPLE.But factorization algorithms over successive algebraic extension fields are still under investigation.The basic factorization algorithm over algebraic extension fields is Trager's algorithm.Algorithms for a single algebraic extension field based on Hensel lifting are given by Weinberger et al.However, in order to compute the irreducible ascending chain in Wu's method,polynomial factorizations over successive algebraic extension fields are needed.Wu,Hu,and Wang independently put forward factorization algorithms over successive algebraic extension fields based on methods of equation solving.Similar to the Trager's algorithm,Wang and Lin proposed another algorithm reducing the problem to the factorization over the rational number field.In their approach, Wu's triangularization algorithm is used,and hence the termination of the algorithm depends on the computation of Wu's method.Zhi applied the lifting technique to the factorization over successive algebraic extension fields.A direct algorithm on factorization over successive alge- braic extension fields is given in this paper,extending Trager's algorithm to factorization over successive algebraic extension fields.The proposed algorithm only uses resultant computation and factorization over the rational number field.