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

Question

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

在那本书的数论章节中，给出了许多算法来测试素数。他展示的最优化的是 O(nloglogn) 中的“Eratosthenes 筛法”。但是他写了一行。我正在翻译它。“在 O(logn) 中有一种更有效的测试素数的方法。自己想一想。如果你没有完成，只需谷歌一下!!”

我用谷歌搜索了它。但我没有找到任何令人满意的东西。

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

Answer 1

这个说法是错误的。对于数字 N，位数是 O(log N)，因此该语句意味着存在一种算法，其位数线性。最著名的结果是位数的多项式。 (Agrawal–Kayal–Saxena 素性检验，Õ(logN ¹²)。这是 logN 的十二次方，而不是一。

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