primes - Miller-Rabin 素性测试的典型运行时间是什么？

Question

我很清楚单个 Miller-Rabin 测试以三次对数时间运行。我知道蒙哥马利模幂和 GNFS 并且我不会问任何那些奇特的理论。我想知道的是，在特征硬件(例如，2.2 GHz Opteron 或某某显卡或 FPGA)上，MR 的一些代表性运行时(请注意，这与 RSA 操作不同)。

Answer 1

在 GMP 中实现的一项基于随机数的 Miller-Rabin 测试，多个素数和多次运行的平均值。 i4770K @ 4.3GHz，GMP 6.0.0a。对于 64 位以下的数字，使用非 GMP 实现(使用 x86_64 asm mulmod)可以更快。这个实现似乎在性能上非常接近大多数其他 C+GMP 实现(对于相同的数字， mpz_aprcl 的 mpz_sprp 运行在下面几个百分比的时间内)。使用非标准 API 调用进行蒙哥马利数学运算可能会更快(也可能不会)。

20 位数字:1.1 美元

40 位数字:3.4 美元

80 位数字:14 美元

200 位:0.11 毫秒

400 位:0.65 毫秒

800 位:4.7 毫秒

1200 位:15 毫秒

1600 位:31 毫秒

2000 位:53 毫秒

4000 位:310 毫秒

通过良好的实现，BPSW(基础 2 M-R + [额外] 强 Lucas 测试)的成本是一次 M-R 测试的约 3 倍。 Lucas 测试实现在性能上有很大不同。 Frobenius 测试的成本约为单个 M-R 测试成本的 2.5 倍。