algorithm - Miller Rabin素性测试有两种类型？

Question

突然遇到两种Miller Rabin素性检验方法。其中一个uses randoms和另一个 does not use randoms .

第二个里面有隐藏的随机生成还是什么？谢谢。

Answer 1

第二个是 deterministic variant Miller-Rabin 素数测试。不使用从随机数生成的“见证”数，而是使用已知足够的素数列表:

When the number n to be tested is small, trying all a < 2(ln n)2 is not necessary, as much smaller sets of potential witnesses are known to suffice"

if n < 3,825,123,056,546,413,051, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, and 23.

这是链接源代码中 alist 中的素数列表。