二元域上多项式的分解算法-Berlekamp算法 matlab实现

以下是Berlekamp算法的matlab实现：

function [factors] = berlekamp(poly)
% BERLEKAMP algorithm for factorization of polynomials over Galois
% field GF(2^n).
%
% Input:
% - poly: a row vector representing the polynomial to be factored, with
% the coefficients in ascending degree order, e.g. [1 0 1 1] for
% x^3 + x + 1.
%
% Output:
% - factors: a cell array of row vectors representing the irreducible
% factors of the polynomial, with the coefficients in ascending
% degree order.

n = length(poly) - 1;
factors = {};

% Set up the Berlekamp matrix.
B = zeros(n, n);
for i=1:n
B(i, i+1:end) = poly(1:n-i);
end

% Initialize the error locator polynomial.
sigma = [1 zeros(1, n)];

% Initialize the discrepancy sequence.
delta = zeros(1, n+1);
delta(1) = 1;

% Initialize the error evaluator polynomial.
psi = [1 0];

% Set up the alpha vector.
alpha = zeros(1, n);
for i=0:n-1
alpha(i+1) = 2^i;
end

% Main loop.
for i=1:n
% Compute the discrepancy.
delta(i+1) = mod(polyval(sigma, alpha(i+1)) + delta(i), 2);

% Compute the error locator polynomial.
if delta(i+1) == 0
% No error, so no update needed.
sigma = mod(conv(sigma, [1 0]), 2);
else
% Update sigma.
temp = mod(conv(psi, fliplr(sigma)), 2);
if length(temp) < length(delta)
temp = [temp zeros(1, length(delta)-length(temp))];
end
sigma = mod(sigma + [zeros(1, i) temp(i+1:end)], 2);
end

% Compute the error evaluator polynomial.
psi = mod(conv(fliplr(delta(1:i+1)), sigma), 2);

% Check for irreducibility.
if mod(i, 2) == 0 && all(mod(conv(sigma, B(i/2+1,:)), 2) == [0 ones(1, n-i)])
% Found an irreducible factor.
factors{end+1} = sigma;
% Update poly.
poly = mod(conv(poly, sigma), 2);
n = length(poly) - 1;
if n == 0
% poly is now 1, so we're done.
return;
end
% Update B.
B = zeros(n, n);
for j=1:n
B(j, j+1:end) = poly(1:n-j);
end
% Update sigma, delta, psi, alpha.
sigma = [1 zeros(1, n)];
delta = zeros(1, n+1);
delta(1) = 1;
psi = [1 0];
alpha = zeros(1, n);
for j=0:n-1
alpha(j+1) = 2^j;
end
end
end

% If we get here, poly is a product of irreducible factors of degree <= 1.
for i=1:n
if poly(i) == 1
factors{end+1} = [1 zeros(1, i-1)];
end
end

end

使用示例：

>> poly = [1 1 1 0 1]; % x^4 + x^3 + x + 1
>> factors = berlekamp(poly)
factors =
[1 1 1]
[1 0 1]

这表示x^4 + x^3 + x + 1 = (x^2 + x + 1)(x^2 + 1)。