求(f,g)
 deg(f)>=deg(g)
 f=g·h+r
 r为0时，(f,g)=g
 r！=0时，(f,g)= (g,r)
 
求(g,r)
 deg(g)>deg®
 g=r·h1+r1
 r1为0时，(g,r)=r
 r1！=0时，(g,r)= (r,r1)
 
……
 r(i-2)=r(i-1)·h(i)+r(i)
 r(i-1)=r(i)·h(i+1)+r(i+1)
 r(i)=r(i+1)·h(i+2)+r(i+2)
 ……
 
设第一个为0的余数为r(i+2)
 (一定会存在一个r(k)使得r(k+2)为0，最坏的情况就是(f,g)=1,使得r(k+2)=0)
 
(f,g)= (g,r)= (r,r1)=…=(r(i), r(i+1))= r(i+1)
 r(i+1)=r(i-1)-r(i)·h(i+1)
 将
 r(i-1)=r(i-3)-r(i-2)·h(i-1)
 r(i)=r(i-2)-r(i-1)·h(i)
 h(i-1)=(r(i-3)-r(i-1)) / r(i-2)
 代入上式
 不断回代可将r(i+1)化为h，r，r1，r2之积进而求(f,g)

 
 
 
文章目录
 
 

  

   

    
最大公因式
    
小结
    
互素
    
最大公因式及互素的推广
    
参考资料
   
 
 
 
 
 

 
多项式01——一元多项式和运算
 
多项式02——整除
 
多项式03——最大公因式与互素
 
多项式04——标准分解式
 
多项式05——多项式函数
 
多项式07——有理系数和整系数多项式
 
最大公因式
 
 

信息论作业中有一道题目要求判断两个生成函数g1(x)和g2(x)构成的(2,1,m)卷积码是否为恶性卷积码。解题的关键是判断两多项式g1(x)和g2(x)是否有非常数的公因式。一种办法是：在GF(2)域上求两多项式的最大公因式。若最大公因式不是常数，则两多项式构成的卷积码是恶性卷积码。
 
在matlab的help文件里查了下，没有找到现成的GF(2)域求两多项式最大公因式的函数，于是自己动手写了一个。代码附在下面。
 
被注释掉的代码是第一个版本。当时不知道有个现成的gfdeconv函数可以直接在GF(2)计算多项式除法，因此写得笨笨的。知道以后就改写现在的样子。不过值得注意的是，与一般的翻卷积函数不同，gfdeconv函数把向量看做升幂排列的多项式。
 
 

 
 
 
clear;
 
%在GF(2)域中求两多项式的最大公因式
 
%注意多项式是降幂排列的还是升幂排列的
 
% b(x) = x^2, a(x) = x^3 + x^2 + 1
 
%降幂排列表示
 
% b = [1 0 0];
 
% a = [1 0 1 1];
 
%升幂排列表示
 
b =  [ 0  0 1];
 
a =  [1  1 0  1];
 
while(sum(b) > 0)
 
    t = b;
 
%注意！conv和deconb函数认为多项式按降幂排列
 
%     [q,r] =deconv(a,b);
 
%     b =mod(r,2);
 
%     ind =find(b,1,'first');
 
%     b =b(ind:end);
 
 
 
%而gfconv和gfdeconv等函数认为多项式按升幂排列
 
%例如[0 0 1]代表x^2
 
    [quot,remd] = gfdeconv(a,b);
 
    b = remd;
 
    a = t;
 
end
 
    
 

大家一般用熟知的欧几里德算法来算最大公约数和公因式，下面介绍一种利用矩阵算最大公因式的方法：
 
一，在开始前先来说几个定理，你可以先看下面的部分，等充满疑惑后再来看这一部分：
 
定理1：（f（x），g（x））=（f（x）±g（x），g（x）±f（x））=（f（x）±g（x），g（x））=（f（x），g（x）±f（x））
 
定理2：如果f（x）=ax^n+bx^n-1+……+cx，那f（x）=x*（ax^n-1+bx^n-2+……+c）。而如果同时（x，g（x））=1，那易得（f（x），g（x））=（f（x）/x，g（x））
 
二，
 
用矩阵算多项式的最大公因式中最重要的2点：
 
 
1，由定理1可得，2个多项式加减不改变最大公因式。
 
2，由定理2可得，移位不变最大公因式。（此时不理解没关系看完下面例子就知道了）
 
例1：求4x^5+4x^4+4x^3+4x^2+4x-20与5x^4+5x^3+5x^2+5x-20的最大公因式
 
系数矩阵
 
4 4 4 4 4 -20
 
0 5 5 5 5 -20
 
运用定理1，将第一行减去第二行
 
4 -1 -1 -1 -1   0
 
0  5  5   5  5 -20
 
再运用定理2将第一行向右移一位，在行首补上0，上下对齐
 
 
0  4 -1 -1  -1  -1
 
0  5  5   5  5 -20
 
再运用定理1使其中一行末尾出现0 
 
0     4   -1   -1   -1  -1
 
0  -75  25   25  25  0   
 
移位
 
 
0   4    -1   -1    -1   -1
 
0   0   -75  25   25  25   （当然，可能已经有人发现了。其实一开始，第一行，和第二行有个公倍数4，5，，貌似把它们提出了也不要紧。对，对于一行的公倍数提出来对结果没影响，只是如果提出来，下面的运算就会出现分数，个人不太喜欢分数，所以没提）
 
就这样反复运用定理1，2，将一行的末尾化为0，再向右移位，最后上述矩阵化为：
 
0  0  0  0  1  -1
 
0  0  0  0  1  -1 这个就说明f（x），g（x）最后可以化成x-1，和x-1，，，公因式即为x-1
 
如果算到最后有一行全为0，但另一行却不全为0，，那就说明2个多项式互素。