Code covered by the BSD License

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

### Jaco Versfeld (view profile)

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

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;

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);

```