是否可以在 O(logn) 内测试一个数是否为素数？

Question

我已经读了一本竞争性编程书籍一个月了。这本书是由我国（孟加拉国）的世界决赛入围者之一撰写的。需要注意的是，这本书是用我们的母语（孟加拉语）写的，在世界范围内并不那么流行。由于内容是孟加拉语，我无法在这里引用。这就是为什么我首先感到抱歉。

在那本书的数论章节中，给出了许多测试素性的算法。他展示的最佳方案是 O(nloglogn) 中的“埃拉托斯特尼筛法”。但他写了一行。我正在翻译它。 “有一种更有效的方法可以在 O(logn) 中测试素性。你自己想一下。如果你没有完成，只需谷歌一下！！”

我用谷歌搜索了一下，但没有找到满意的东西。

真的有可能在 O(logn) 时间内测试一个数的素数吗？ 如果可能的话，可以得出多大范围的结论？？

Answer 1

该说法不正确。对于数字 N，位数为

O(log N)

，因此该陈述意味着存在一种在位数上是线性的算法。最著名的结果是位数的多项式。 （Agrawal–Kayal–Saxena 素性测试，Õ(logN ¹²)。这是 logN 的 12 次方，而不是 1。

仍然，Õ(logN ¹²) ⊂ O(N)

Answer 2

是的，本书作者是正确的，您可以使用Miller-Rabin 大数素性测试对大于 0(logn) 的数字 n 进行素性测试。您可以在谷歌上搜索此测试以了解更多信息。