Gcd на полиноми по модул k

Ето една проста реализация. Полиномите са кодирани като масиви от коефициенти, като се започне от най-ниската степен: така че x^4+x^3+2x+2 е [2 2 0 1 1]. Функцията взема два полинома p, q и модула k (който трябва да бъде прост за свойството да работи алгоритъмът).

Примери:

• gcdpolyff([2 2 0 1 1], [1 1 1 1], 3) връща [1 1], което означава 1+x.
• gcdpolyff([2 2 0 1 1], [1 1 1 1], 5) връща [1 3 2], което означава 1+3x+2x^2; това не е в съответствие с вашия отговор, но аз проверих на ръка и изглежда, че вашият е грешен.

Функцията първо допълва масивите да бъдат с еднаква дължина. Докато те не са равни, is идентифицира полинома от по-висока степен и изважда от него полинома от по-ниска степен, умножен по подходяща степен на x. Това е всичко.

function g = gcdpolyff(p, q, k)
p = [p, zeros(1, numel(q)-numel(p))];
q = [q, zeros(1, numel(p)-numel(q))];
while nnz(mod(p-q,k))>0
    dp = find(p,1,'last');
    dq = find(q,1,'last');
    if (dp>=dq)
        p(dp-dq+1:dp) = mod(p(1+dp-dq:dp) - q(1:dq), k);
    else
        q(dq-dp+1:dq) = mod(q(dq-dp+1:dq) - p(1:dp), k);
    end
end
g = p(1:find(p,1,'last'));
end

Имената на променливите dp и dq са леко подвеждащи: те не са степени на p и q, а по-скоро степени + 1.