Extended Euclidean Algorithm for polynomials over GF(2^m)

by

 

Implementation of the extended Euclidean algorithm for polynomials over GF(2^m)

comp_gcd(m,n,field)
function [g,u,v] = comp_gcd(m,n,field)

%compute gcd(m,n) = u*m + v*n
%Try to convert algorithm to polynomials over GF(2^m)

a1 = m;
a2 = n;

%initial values
x1 = 0;
x2 = -Inf;
y1 = -Inf;
y2 = 0;


q2 = gfdeconv(m,n,field);

%matrix = [a(1) 0 x(1) y(1); a(2) q(2) x(2) y(2)]

%disp('output')
%a1
%0
%x1
%y1

%disp('output')
%a2
%q2
%x2
%y2


a3 = gfadd(a1,gfconv(a2,q2,field),field);


compare_a3 = [];
while length(compare_a3) ~= length(a3)
    compare_a3 = [compare_a3 -Inf];
end


while all(compare_a3 == a3) ~= 1
    
    q3 = gfdeconv(a2,a3,field);
    
    %q3 = buffer_q3;
    
    x3 = gfadd(x1, gfconv(q2, x2, field), field);
    
    
    
    y3 = gfadd(y1, gfconv(q2, y2, field), field);
    
    
%     
%     %matrix = [matrix; a(el) q(el) x(el) y(el)];
%     disp('output')
%     a3
%     q3
%     x3
%     y3
%     
    
    %Swop the buffers
    
    q1 = q2;
    q2 = q3;
    
    x1 = x2;
    x2 = x3;
    
    y1 = y2;
    y2 = y3;
    
    a1 = a2;
    a2 = a3;
    g = a3;
    a3 = gfadd(a1,gfconv(a2,q2,field),field);
    
    compare_a3 = [];
    while length(compare_a3) ~= length(a3)
        compare_a3 = [compare_a3 -Inf];
    end
end

%matrix
%g = a(el-1);

g = gfconv(g,0,field);

g_inv = gfdiv(0,g(length(g)),field);

g = gfconv(g_inv,g,field);
u = gfconv(x3,g_inv,field);
v = gfconv(y3,g_inv,field);

Contact us