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

Question

我很清楚单个Miller-Rabin测试是在立方对数时间内运行的。我知道Montgomery模幂运算和GNFS，我不是在问任何花哨的理论。我想知道的是，在特征硬件(例如，2.2 GHz Opteron或某某图形卡或FPGA)上，MR的一些代表性运行时间(请注意，这与RSA操作不同)。

Answer 1

在GMP中实现的一个随机基米勒-拉宾测试，多个素数和多次运行的平均值。i4770K @4.3 GMP，GMP6.0.0a。对于64位以下的数字，使用非GMP实现(使用x86_64 asm mulmod)可以更快。这个实现似乎在性能上与大多数其他C+GMP实现非常接近(对于相同的数字，mpz_aprcl的mpz_sprp运行时间是下面的几个百分点)。

• 20位: 1.1 uS
• 40位: 3.4 uS
• 80位: 14 uS
• 200位: 0.11 mS
• 400位: 0.65毫秒
• 800位: 4.7 mS
• 1200位: 15毫秒
• 1600位: 31毫秒
• 2000位: 53毫秒
• 4000位: 310毫秒

有了很好的实现，BPSW (base 2 M-R + extra strong Lucas test)的成本大约是一次M-R测试的3倍。Lucas测试实现在性能上有很大的不同。Frobenius测试的成本大约是单个M-R测试的2.5倍。

Answer 2

米勒-拉宾测试的一轮可能需要大约1毫秒；这里有一个JavaScript的交互式实现，您可以在浏览器中运行它并自己检查计时：http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm