文章目录

一、解析二、思路三、演示图四、代码1、Main2、Poly_GCD3、Poly_Division4、Poly_Multi5、Poly_Multi_Eye

一、解析

Poly_GCD(r1,r2,nums)：

接收多项式r1,r2(r1>=r2),以及多项式长度nums

返回其每一步的商组成的矩阵Q,以及gcd(r1,r2)

Poly_Division(r1,r2,nums)：

接收多项式r1,r2(r1>=r2),以及多项式长度nums

返回商，及其余数

Poly_Multi(a,b,nums)：

接收多项式a,b,以及多项式长度nums

返回乘积

Poly_Multi_Eye(a,b,nums)：

接收多项式a，仅有一个系数为1的多项式b,以及多项式长度nums

返回乘积

二、思路

函数Poly_GCD(r1,r2,nums)返回其商的矩阵Q，以及最大公因式gcd

X初始迭代值为gcd，Y初始迭代值为任意多项式

设X初始迭代值为gcd，Y初始迭代值为0

迭代方程如下：

Next_X=Y

Next_Y=X-Q_i*Y

单击查看迭代方程证明

最终输出X,Y迭代值

三、演示图

四、代码

1、Main

nums=9;r1=[0 1 0 0 0 0 0 1 1];r2=[1 0 0 0 1 1 0 1 1];%高次在前，低次在后[Q,gcd]=Poly_GCD(r2,r1,nums);Size=size(Q);X=gcd;Y=zeros(1,nums);for i=1:Size(1)temp1=Y;temp2=xor(X,Poly_Multi(Q(i,:),Y,nums));X=temp1;Y=temp2;enddisp(X);disp(Y);

2、Poly_GCD

function [Q,r2] = Poly_GCD(r1,r2,nums)Q=[];[q,r3]=Poly_Division(r1,r2,nums);Q=[q;Q];while(~(max(r3)==0))r1=r2;r2=r3;[q,r3]=Poly_Division(r1,r2,nums);Q=[q;Q];endend

3、Poly_Division

function [Q,r3] = Poly_Division(r1,r2,nums)Q=zeros(1,nums);temp1=find(r1==1);temp2=find(r2==1);temp3=temp2(1)-temp1(1);while(temp3>=0)q1=zeros(1,nums);q1(1,nums-temp3)=1;Q=Q+q1;Poly_Multi(r2,q1,nums);r3=xor(r1,Poly_Multi(r2,q1,nums));if(max(r3)==0)break;endr1=r3;temp1=find(r1==1);temp3=temp2(1)-temp1(1);endend

4、Poly_Multi

function [ret] = Poly_Multi(a,b,nums)temp1=find(b==1);Size=size(temp1);ret=zeros(1,nums);for i=1:Size(2)temp2=zeros(1,nums);temp2(1,temp1(i))=1;ret=xor(ret,Poly_Multi_Eye(a,temp2,nums));endend

5、Poly_Multi_Eye

function [ret] = Poly_Multi_Eye(a,b,nums)temp1=find(b==1);for i=1:nums-temp1(1)a(1,1:nums-1)=a(1,2:nums);a(1,nums)=0;endret=a;end`