Raku 的 is-prime 函数有多可靠？

Question

Raku 函数的文档说明is-prime如下：

如果已知此 Int 是素数，或者根据概率 Miller-Rabin 测试很可能是素数，则返回 True。

如果已知此 Int 不是素数，则返回 False。

我在 Raku 中进行了大量的代码编程，对于许多问题来说，有一个内置的方法来测试素性是非常方便的。例如，要获取素数的惰性无限序列：

my @primes = grep &is-prime, ^Inf;

然而，有时我会因为文档中所说的“如果此 Int 为素数则返回 True，否则返回 False”以外的内容而感到困扰。事实上，该措辞似乎承认可能​​存在误报或漏报。

真的有多可靠is-prime？

Answer 1

Raku 使用 Miller-Rabin 素数测试，该测试检查潜在素数是否在不同碱基中可能是素数，并且它可能是素数的碱基越多，它实际上是素数的可能性就越大。其精度至少为 1\xc2\xa0\xe2\x88\x92\xc2\xa04 ^{\xe2\x88\x92 k}，其中k是运行的迭代次数。我无法找到 Raku 运行的实际迭代次数，可能很多。但无论如何，围绕 Miller-Rabin 主要测试的普遍观点是，它足以满足实际使用的需要，但不要将其用于任何与加密或其他安全相关的事情。

\n

我个人认为对于代码高尔夫来说已经足够好了 - 这是一种语言功能，如果人们想对此挑剔，那么你可以编写自己的 Raku 版本，除了将素性测试替换为真正的素数测试之外，它是完全相同的。

\n