多项式模 k 的 Gcd

Question

我想请Matlab告诉我，例如，x^4+x^3+2x+2和x^3+x^2+x+1多项式的最大公约数Z_3[x]（答案是 x+1）和 Z_5[x]（答案是 x^2-x+2）。

有什么想法可以实现吗？

Answer 1

这是一个简单的实现。多项式被编码为系数数组，从最低阶开始：因此，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) returns [1 1] 表示 1+x.
gcdpolyff([2 2 0 1 1], [1 1 1 1], 5) returns [1 3 2] 表示1+3x+2x^2；这不同意你的回答，但我亲手检查了一下，你的回答似乎是错误的。

该函数首先将数组填充为相同长度。只要它们不相等，就是识别高次多项式并从中减去乘以 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。

多项式模 k 的 Gcd

Gcd of polynomials modulo k

matlab

algebra

finite-field

polynomials