数的原根

Question

我已经尝试实现 here 中描述的算法来寻找素数的原根。

它适用于小质数，但是当我尝试大数时，它不再 return 正确答案。

然后我注意到 a^(p-1)/pi 往往是一个大数字，它在 MATLAB 中 returns inf，所以我认为因式分解 (p-1) 会有所帮助，但我我没看到如何。

我用 MATLAB 写了一小段代码，就在这里。

clear all
clc

%works with prime =23,31,37,etc.

prime=761; %doesn't work for this value

F=factor(prime-1); % the factors of prime-1
 for i = 2: prime-1
        a=i;
        tag =1;
        for j= 1 :prime-1
            if (isprime(j))
                 p_i = j;
                 if(mod(a^((prime-1)/p_i),prime)== 1)
                     tag=0;
                     break 
                else
                    tag = tag +1;
                 end
            end
        end
        if (tag > 1 )
            a %it should only print the primitive root
            break
        end
end

欢迎任何意见。谢谢

Answer 1

Matlab 在这种情况下所做的是在取模之前计算 a^((p-1)/p)。由于 a^((p-1)/p) 很快变得太大而无法处理，Matlab 似乎通过将其转换为浮点数来解决此问题，从而失去一些分辨率并产生取模时的错误结果。

如@rayreng 所述，您可以使用任意精度工具箱来解决此问题。

或者，您可以将取幂分成几个部分，在每个阶段取模。这应该更快，因为它占用的内存更少。您可以将它转储到一个函数中，然后调用它。

% Calculates a^b mod c
i = 0;
result = 1;

while i < b
    result = mod(result*a, c);
    i = i + 1;
end

数的原根

Primitive root of a number

matlab

cryptography

primes

public-key-encryption