求解多项式最大公因式的一个算法

第27卷第5期广西民族师范学院学报

Vol.27No.5求解多项式最大公因式的一个算法

农利伟

（南宁地区教育学院数学系，广西

南宁

530001）

摘要：研究了用辗转相除法求解多项式最大公因式的一个迭代算法。算法将两个多项式相乘，相除等过程用矩阵方法来处理，从而获得了用Matlab软件求解多项式最大公因式的迭代算法。

关键词：多项式；最大公因式；迭代算法；辗转相除法；Matlab中图分类号：TP391文献标识码：A文章编号：1674-8891（2010）05-0004-02

IterativeAlgorithmfortheGreatestCommonFactorofPolynomial

（DepartmentofMathematics,NanningPrefecture’sEducationalCollege,Nanning，Guangxi530001,China）

NongLi-wei

Abstract：Thisthesisresearchesoniterativealgorithm,whichgivesasolutiontothegreatestcommonfactorofpolynomialoneuclideanalgo-rithm.Withpolynomialsmultipliedanddivided,bythematrixapproach,aniterativealgorithmisachievablebymeansofMatlabasaresultoffillingtheblankofsolvingthegreatestcommonfactorofpolynomialwithMatlab.

Keywords：polynomial,thegreatestcommonfactor;iterativealgorithm;euclideanalgorithm;Matlab.

0引言

多项式最大公因式的求解是多项式理论中的核心部分，许多实际问题最终常常归结为求解多项式的最大公因式，因此，设计多项式最大公因式的有效算法是十分必要的。以求解多项式最大公式的辗转相除法理论为基础，结合MATLAB的特点，设计出可以有效求解多项式最大公因式相关问题的一个算法，且此算法编程简单，方便实用，容易推广。

rk-1（x）=rk（x）qk+1（x）

其中r1(x)≠0(i=1,2,…,k)，根据最大公因式的性质可知rk(x)是f(x)与g(x)的一个最大公因式。由(2)中倒数第2个式子解出rk(x)，再由(2)中倒数第3个式子解出rk-1(x)，利用逐步代人法可求得(1)中的u(x)和v(x)。2辗转相除法中的三个变形

传统求解多项式最大公因式的辗转相除法是基于用笔与纸计算的，要想用电脑来计算,需要改革用笔和纸计算中的无规律性。为此，对两个多项式相乘的方法，求商式与余式的方法，求和逐步代人法等传统方法进行变形，以获得迭代算法。下面以f(x)=2x3+3x+1，g(x)=x2+2x+1为例来说明算法中的一些变形。

1传统求解多项式最大公因式的辗转相除法

以F(x)表示数域F上的一元多项式环。设f(x)与g(x)都是数域F上的一元多项式，且f(x)的次数大于或等于g(x)的次数，

要求出F(x)中的多项式

u(x)与v(x)，使

(f(x),g(x))=u(x)f(x)+v(x)g(x)

成立的辗转相除法如下：

(1)2.1两个多项式相乘法的变形

与相乘按如下格式计算

用g(x)除f(x)得商式与余式r1(x)；如果r1(x)≠

0，则再用r1(x)除g(x)，又可以得到商式q2(x)与余式r2(x)；如此辗转相除下去，由于余式的多顶式次

数越来越小，因此在有限次以后，必有一个余式为

2xÁ+0xÂ+3x+11x

+2x+4x

0。于是得到下面的等式组，

f（x）=g（x）q1（x）+r1（x）g（x）=r1（x）q2（x）+r2（x）rk-2=rk-1（x）qk（x）+rk（x）

2xÃ+0xÄ+3xÁ1xÂ

ÄÁÂ

（2）

2xÁ+0xÂ+3x+1

2xÃ+4xÄ+5xÁ+7xÂ+

5x+1

收稿日期：2010-6-16

作者简介：农利伟(1965-)，男，壮族，广西天等人，南宁地区教育学院讲师，主要研究方向：矩阵方程迭代算法的构造与分析。

-4-

2010年第5期农利伟求解多项式最大公因式的一个算法10月25日出版

------------------------------------------------------------

n=length(f);

有了上面的图示，只须用下面简单的Matlabm=length(g);程序即可获得f(x)与g(x)相乘的结果。fori=1:n;forj=1:m

h(i,j+i-1)=g(j);f=[2031]；g=[121];

end;endfori=1:3；forj=1:4;

L=n-m+1;%L表示g(x)除f(x)h(i,j+i-1)=f(j)*g(i);

%所得的商式中末知量的个数.end；end

h=sum(h).a=[h([1:L],[1:L]);f([1:L])]';程序运行后的结果为h=[2,4,5,7,5,1]。t=length(a);

hx=rref(a);

2.2求商式与余式的变形hx=hx(:,t);

q=hx';%q是g(x)除f(x)所得的商式.

用f(x)除g(x)，求商式q1(x)与余式r1(x)。传forj=1:m;fori=1:n-m+1统方法是用竖式除法,它的主要缺点是不容易找w(i,j+i-1)=hx(i)*g(j);出规律，现在改用待定系数法求解。设q1(x)=end;enda1x+a0,r1(x)=b1x+b0，借助上面两个多顶式相乘的ifn-m+1>1格式，需要求解下列矩阵方程：w=sum(w);

end1210

+(0,0,b1,b0)(2,0,3,1)=(a1,a0)r=f-w;

0121

qx=poly2sym(q);

12A=[01;1-qx]*A;2,0(a,a)=()ÁÂ01而得首先通过解方程

ifabs(r)

到a1,a0，再解下列方程而得到,

d=g./g(1);

1210Z=[1/g(1),0;01]*A;(0,0,bÁ,bÂ)=(2,0,3,1)−(aÁ,aÂ)0121u=sym2poly(Z(1,1));v=sym2poly(Z(1,2));

return;else这样可获得(2)中各q1(x)与r1(x)的迭代算法。

k=find(abs(r)>10^(-10));2.3逐步代人法的变形

r(1:k(1)-1)=[];%r是g(x)除f(x)所得的余式.为了找出(2)中r1(x)与f(x),g(x)的关系，需要

end把（2）中的等式改写为矩阵相乘的等式形式，比如

f=g;g=r;w=[];h=[];把f(x)=g(x)q1(x)+r1(x)改写为

(x)1g(x)endf(x)qÁ

g(x)=



故f(x)g(x)=2x5+4x4+5x3+7x2+5x+1。

r(x)0Á

这样我们找到了与，的递推关系：

4结束语

(x)010101f(x)rÁ=