AKS素性测试是否非多项式时间算法？对《PRIMES is in P》论文步骤存疑

你提的这个点真的是理解该算法时间复杂度的关键——很多人一开始都会被朴素算法的高复杂度误导，但实际上判断n是否可表示为a^b（b>1） 完全可以在多项式时间内完成，核心是要搞清楚算法复杂度里的“多项式时间”是针对输入的长度（即n的位数），而不是n本身的数值。

先澄清一个核心概念：算法复杂度的基准 #

我们说一个算法是多项式时间，指的是它的时间复杂度是输入长度k的多项式函数，其中k是n的二进制位数，也就是k=⌈log₂n⌉。比如O(k³)、O(k²logk)都是多项式时间，但O(n)（也就是O(2^k)）是指数时间，这是完全不同的量级。你提到的朴素O(n²)算法是针对n的数值而言的，这显然是指数级的，但我们根本不需要用这种低效的方法。

高效判断完全幂的具体步骤 #

我们可以用以下思路在多项式时间内完成判断：

• 限制b的取值范围：因为a≥2，所以2^b ≤n → b≤log₂n=k。也就是说b的取值只需要从2到k，总共只有O(k)个可能的取值，k是n的位数，这是多项式级别的数量。
• 对每个b，用二分查找找a：对于固定的b，我们需要找是否存在整数a∈[2, n^(1/b)]使得a^b =n。这里可以用二分法在这个区间内查找，每次计算a^b的时候用快速幂算法，并且在计算过程中如果中间结果超过n就直接终止（避免不必要的计算）。快速幂的时间复杂度是O(log b)，而b≤k，所以每次计算的时间是O(log k)。
• 总复杂度计算：总共有O(k)个b需要检查，每个b的处理时间是O(log k)，所以总时间复杂度是O(k log k)，这显然是输入长度k的多项式函数，完全符合多项式时间的要求。

额外补充：更优化的小技巧 #

实际实现中还可以进一步优化，比如：

• 先检查小的b值（比如b=2,3,...,直到b>log₂n），一旦找到符合条件的a就直接返回结果，不需要遍历所有b；
• 利用数论中的性质，比如先判断n是否为平方数、立方数等，再处理更大的b，进一步减少计算量。

总之，这个步骤的关键是跳出“针对n的数值做遍历”的思维，转而从输入长度（位数）的角度设计算法，这样就能把复杂度降到多项式级别。

内容的提问来源于stack exchange，提问作者M Smith