Question

引用Marsaglia先生关于为CMWC PRNG生成更多参数：

“那些想要更多对r，a的人需要找到形式为p=ab^r+1的素数，其中b=2^32-1是其原始根”。

我的问题在于我应该用什么方法来做这件事。尤其是非常大的素数。这是我在MATLAB中写的：

isPrimitiveRoot = 0;
goodParameters = zeros(1,vectorSize);
nextFreeSpace = 1;
r = 1;
b = 2^32-1;
for a=0:2^32-1
  isPrimitiveRoot = 0;
  number = a*b^r+1;
  if(isprime(number))
    p = number;
    phi_p = p - 1;
    factors = factor(phi_p);
    isPrimitiveRoot = 1;
    for i=1:length(factors)
      if(isprime(factors(i)))
        if(mod(b^(phi_p/factors(i)),p)==1)
          isPrimitiveRoot = 0;
        end
      end
    end
  end
  if(isPrimitiveRoot)
    goodParameters(nextFreeSpace) = a;
    disp([nextFreeSpace a]);
    nextFreeSpace = nextFreeSpace + 1;
  end
end

我这样做是因为为某个r滞后找到好的a参数的步骤是：

Prove that p = a*b^r+1 is prime
Prove that b is a primitive root of p. For that you need to evaluate the prime factors of p-1 and verify that b^((p-1)/p_i) =/= 1 (mod(p)) for all p_i prime factors of p-1.

现在很明显为什么脚本不起作用了。我选择了b=2^32-1，并选择了滞后r=1b^（phi_p/factors（i））会产生太大的数字（Inf）。

What should I be doing instead?
Should I be using another software?
Is there another algorithm for verifying primitive roots?

Answer 1

嗯，人们总是可以使用我的vpi在matlab中的工具箱。虽然我没有提供一个显式生成/测试基根的工具，但vpi确实能够处理任意大的整数，以及一个powermod函数来完成大部分工作。

然而，我要指出的是，在2^32个元素上进行简单的强力循环需要一段时间才能完成，无论工具如何。

友情链接