有限域内求解多项式的周期

Question

对于有限域Z/(m)内的多项式f(x),其周期T应满足f(x)|x^T-1

我让T从1开始递增,目的是找到使得余式为0的最小的T

有限域求多项式周期代码:

function [T] = Cycle(m,A)   %m为有限域的模数,A为多项式系数向量,T为周期返回值
T=1;
a0=A(length(A));
if a0<0
    a0=a0+m;
end
b=zeros(1,T+1);           %b为x^T-1的系数向量
b(1)=1;
b(T+1)=-1;
[~,r]=deconv(b,A);
a=find(r,length(r));
c=isempty(a);
if isempty(intersect(a0,m))==1
    while (c==0)
    T=T+1;
    b=zeros(1,T+1);
    b(1)=1;
    b(T+1)=-1;
    [~,r]=deconv(b,A);
    r=mod(r,m);
    a=find(r,length(r));
    c=isempty(a);
    end
end
end

我的代码当f(x)的系数很大时求得的余式向量中含有NaN错误,小弟觉得是deconv函数的问题.

希望问题可以得到解决.

Answer 1

你的代码中的问题可能出现在使用deconv函数时对系数的处理上。deconv函数在计算多项式除法时，对于特别大的系数会产生数值溢出的情况，导致得到的余式向量中存在NaN。为了解决这个问题，你可以尝试对输入的多项式系数进行归一化处理，使其在一定范围内，避免数值溢出。

具体而言，可以将系数向量A中的每个系数除以A中的最大系数，将其归一化到0到1之间。然后在使用deconv函数计算余式时，将得到的余式向量再乘以最大系数，恢复到原始的数值范围。

以下是你的代码在这方面的修改建议：

function [T] = Cycle(m,A)
    % 对多项式系数进行归一化处理
    max_coef = max(abs(A));
    A_normalized = A / max_coef;

    T=1;
    a0=A_normalized(length(A_normalized));
    if a0<0
        a0=a0+m;
    end
    b=zeros(1,T+1);
    b(1)=1;
    b(T+1)=-1;
    [~,r]=deconv(b,A_normalized);
    r = r * max_coef;
    a=find(r,length(r));
    c=isempty(a);
    if isempty(intersect(a0,m))==1
        while (c==0)
            T=T+1;
            b=zeros(1,T+1);
            b(1)=1;
            b(T+1)=-1;
            [~,r]=deconv(b,A_normalized);
            r = mod(r,m);
            r = r * max_coef;
            a=find(r,length(r));
            c=isempty(a);
        end
    end
end

这样修改后，应该能避免deconv函数产生NaN错误的问题。希望对你有帮助！