algorithm - 是否有多项式时间算法来测试某个数是否为某个数的指数？

Question

只要研究那篇著名的论文PRIMES is in P，就会感到困惑。

所提出算法的第一步是If (n=a^b for nature number a and b>1), output COMPOSITE.由于整个算法在多项式时间内运行，因此这一步也必须在 O((log n)^c) 内完成（给定输入大小为 O(log n)。但是，我无法弄清楚谷歌搜索后命中目标的任何算法。

问题：

是否有任何算法可用于测试多项式时间内某个其他数字的指数是否为指数？

谢谢和最好的问候！

Answer 1

如果n=a^b（对于 a > 1）然后 b ≤ log ₂ n，我们可以检查 allb的小于log n来测试这个，我们可以迭代以查找b从 2 到 log n，并且为了找到a我们应该在 1..平方（n）。但是二分查找需要 O( logn) 时间进行迭代，最后在每个搜索步骤中（对于任何找到a的检查）我们应该检查是否 a ^b == n 并且这需要 O(log n)，所以总搜索时间将为 O （日志³ ñ）。可能有更快的方法，但是通过知道AKS是 O(log ⁶ n) 这个 O(log ³ n) 不会伤害任何东西。

Answer 2

如果存在 b^e = n 的 b 和 e，则数 n 是完美幂。例如 216 = 6^3 = 2^3 * 3^3 是完美幂，但 72 = 2^3 * 3^2 不是。确定一个数是否为完美幂的诀窍是要知道，如果该数是完美幂，则指数 e 必须小于 log2 n，因为如果 e 大于则 2^e 将大于 n。此外，只需要测试素数 e，因为如果一个数是复合指数的完美幂，它也将是复合分量的素因数的完美幂；例如，2^15 = 32768 = 32^3 = 8^5 是一个完美的立方根，也是一个完美的五次根。因此，该算法是制作一个小于 log2 n 的素数列表并测试每个素数。由于 log2 n 很小，并且素数列表更小，因此即使对于较大的 n，这也没什么用。

你可以在这里看到一个实现。

Answer 3

public boolean isPerfectPower(int a) {
    if(a == 1) return true;
    for(int i = 2; i <= (int)Math.sqrt(a); i++){
        double pow = Math.log10(a)/Math.log10(i);
        if(pow == Math.floor(pow) && pow > 1) return true;
    }
    return false;
}