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

Question

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

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

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

真的有可能在 O(logn) 中测试一个数的素数吗？如果可能的话，那么可以得出的结论是在什么范围内？

Answer 1

该说法不正确。对于数字 N，位数为O(log N)，因此该陈述意味着存在一种与位数呈线性的算法。最著名的结果是位数的多项式。（Agrawal\xe2\x80\x93Kayal\xe2\x80\x93Saxena 素性测试，\xc3\x95(logN ¹² )。这是 logN 的十二次方，而不是一。

\n\n

尽管如此， \xc3\x95(logN ¹² ) \xe2\x8a\x82 O(N)

\n