采用牛顿插值的多项式因式分解算法的设计与实现.pdfVIP

计算机时代 2009 年 第11 期 ·9 · 采用牛顿插值的多项式因式分解算法的设计与实现 李治强，龙法宁 (玉林师范学院数学与计算机科学系，广西 玉林 537000) 摘 要：基于Kronecker 所提供的一元多项式因式分解的构造算法、一元整系数多项式在整数环上因式分解理论，利用 牛顿向前差分插值算法代替拉格朗日插值算法，把有理域上一元高次多项式因式分解化为在整数环上的因式分解，得到 了整数环上的一元多项式因式分解的构造性算法，给出了具体实现过程。 关键词：Newton 插值；不可约多项式；因式构造；算法 Design and Implementation of Polynomial Factorization Algorithm Using Newton Interpolation LI Zhi-qiang ，LONG Fa-ning （Dept.ofMathematicsandComputerScience,YulinNormalUniversity,Yulin,Guangxi 537000, China） Abstract ：Based on the constructive algorithm of one-place polynomial factorization provided by Kronecker and the factorization theory of one-place integer coefficients polynomial over integer ring, replacing Lagrange interpolation algorithm with Newton forward difference interpolation algorithm, the factorization of one-place high order polynomial over rational number field is transformed into the factorization over integer ring, then the constructive algorithm and implementation procedure of one-place polynomial factorization over integer ring are obtained. Key words ：Newton interpolation ；irreducible polynomial ；factor structure ；algorithm 0 引言 解题效率。 多项式因式分解的构造和算法是计算机代数的重要课题， 1 算法原理分析 对此国内外很多学者做了大量的工作。例如，吴文俊教授在文 1.1 Newton向前差分插值算法 献[2]中作了系统详细的研究，给出因式分解方法。A.K. 在Kronecker提供的因式分解构造性算法中，采用了拉格 Lenstra,H.K.Lenstra和L.Lovasz三人于1982年首次提出了一元 朗日插值算法。拉格朗日插值算法虽然格式整齐和规范，但计