matlab - 多项式的 Gcd 模 k

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)返回[1 1]含义 1+x。
• gcdpolyff([2 2 0 1 1], [1 1 1 1], 5)返回[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。