SSMR

SSMR（Single-Shot Miller-Rabin）是一种仅使用单个强费马检验来检查某个数是否为素数的算法。与相关的Machine-prime一样，它提供了两个函数，is_prime和is_prime_wc。is_prime针对平均情况进行优化，除了费马检验外，还使用试除法。is_prime_wc针对检查质数的最坏情况进行优化，但它可能会通过合数。这是因为检查是否能被2整除非常快，而且仅对奇数合数进行测试，我们可以将测试间隔加倍。此外，由于is_prime_wc的大多数应用永远不会遇到偶数合数，这也是事实。

与Machine-prime一样，它也是使用F-Analysis构建的，但由于原始算法已更改，因此它可能无法重现（也不需要，因为证明正确性比重新计算要快得多）。

属性

• 界限 - 2^40或109万亿
• is_prime_wc偶数合数通过 - 36
• is_prime平均复杂度 - 0.21xFermat
• is_prime_wc最坏/平均复杂度 1.0xFermat
• 与大多数素性检验不同，这两个函数都被彻底证明与文档中的描述完全一致，这是由于间隔很小且速度很快才得以实现。
• SSMR似乎是迄今为止单次Miller-Rabin检验的最大间隔，之前的记录比这个间隔小256倍以下

应用

is_prime

• 在区间内测试其他素性检验
• 确定特定形式的质数

is_prime_wc

• 测试筛法。筛法可以非常快速地生成大量质数，因此使用一个验证质数快速的测试是理想的
• 测试可能质数，例如部分分解的结果

可能的研究应用

• 寻找Carmichael数。Webster和Shallue计算了直到10^22的Carmichael数，由于因子不能大于sqrt(n)，因此SSMR可以用来找到10^24的Carmichael数。
• 生成用于构建素性检验的特殊半质数，例如形式为(ak+1)(k+1)的数

缺点

遗憾的是，SSMR（斯梅尔定理）目前存在一个上限，这阻碍了其在严肃研究中的应用。专门设计的筛法在几乎所有应用中都将优于SSMR，主要的障碍在于设计这样的筛法的难度。此外，像Kim Walisch的primesieve这样的通用筛法已经能够几乎瞬间筛出高达2^40的数，这使得SSMR在生成某些区间内的素数（机器素数用途）方面实际上变得无用。

这个问题意味着SSMR目前仅限于娱乐应用，然而这可能对于大多数非专业应用来说已经足够。除了研究之外，很少需要每秒生成90万个素数。