确定 N 是否为幂的多项式（以 n 为单位）时间算法

Question

我是一名计算机科学专业的学生；我正在自学算法课

在课程中，我看到了这个问题：

Given an n-bit integer N, find a polynomial (in n) time algorithm that decides whether N is a power (that is, there are integers a and k > 1 so that a^k = N).

我想到了第一个 n 为指数的选项：对于所有 k ， 1

例如，如果N = 27，我会从k = 2开始，因为2不整除27，我会去下一个k = 3。我将除以 27 / 3 得到 9，然后再除以得到 1。这不是一个好的解决方案，因为它是 n 的指数。

我的第二个选择是使用模块化算法，使用 a^k ≡ 1 mod (k+1) if gcd(a, k+1 ) = 1 (欧拉定理）。不知道a和k是不是互质

我正在尝试编写一个算法，但我很难做到：

function power(N)
Input: Positive integer N
Output: yes/no
Pick positive integers a_1, a_2, . . . , a_k < N at random
if (a_i)^N−1 ≡ 1 (mod N)
for all i = 1, 2, . . . , k:
    return yes
else:
    return no

我不确定算法是否正确。我怎样才能正确地写这个？

Answer 1

忽略 N 为 0 或 1 的情况，您想知道 N 是否可表示为 a^b for a>1, b>1。

如果你知道 b，你可以在 O(log(N)) 算术运算中找到 a（使用二进制搜索）。包括求幂在内的每个算术运算都在 log(N) 的多项式时间内运行，因此这也是多项式的。

可以绑定b：最多可以是log_2(N)+1，否则a会小于2。

所以只需尝试从 2 到 floor(log_2(N)+1) 的每个 b。每次尝试都是 n 的多项式 (n ~= log_2(N))，并且有 O(n) 次试验，所以结果时间是 n 的多项式。

Answer 2

这看起来像是一道简单的数学题。假设我们得到的 N = 96889010407 远小于 Number.MAX_SAFE_INTEGER.

该问题试图弄清楚 N 是否是 a**k === N 对 a > 1 和 k > 1 的幂。所以我们也可以写成

Math.log(a**k) === Math.log(N) 产生 k*Math.log(a) === Math.log(N) 产生 Math.log(a) === Math.log(N) / k 其中 k 是整数 > 1.

现在记住反对数。 Math.log(y) = x 产生 y = Math.E**x.

这意味着我们正在为某些 k 寻找像 a = Math.E**(Math.log(N) / k) 这样的整数（如果存在的话）。所以从 k=2 开始，递增 1。

 k  a = Math.E**(Math.log(N) / k)
___ _____________________________
 2  311269.99599543784    ->   NO
 3  4592.947769836504     ->   NO
 4  557.9157606623403     ->   NO
 5  157.49069663608586    ->   NO
 6  67.77129015915592     ->   NO
 7  37.1080205641031      ->   NO
 8  23.62024048697092     ->   NO
 9  16.622531664172815    ->   NO
 10 12.54952973764698     ->   NO
 11 9.971310247420734     ->   NO
 12 8.232332000056601     ->   NO
 13 6.999999999999999     ->   YES a is 7 and 96889010407 = 7^13

那么我们需要迭代多长时间？只要Math.E**(Math.log(N) / k >= 2。在这种情况下，最多 36 次迭代，因为 Math.E**(Math.log(96889010407) / 37 是 1.9811909632660634 并且 a 必须是整数 > 1。

这个算法可能是完成这项工作最有效的算法。当我们迭代 k（幂）时，它的时间复杂度是 O(log2(N))。如果我们选择 a 进行迭代，那么时间复杂度将是 O(sqrt(N)).

这适用于自然数，但您也可以将其扩展到有理数。

话说，10.999671418529301是完美的力量吗？

你只需要将小数化成分数the best way possible得到有理式4084101/371293，将分子和分母都应用到上面提到的算法中，看看是否他们都提供相同的权力，在这种情况下将是 5。 10.999671418529301 是 21^5/13^5.

注意：示例中使用了JS Math对象

Answer 3

N不能超过2^n。因此，您可以初始化 i=2、j=n 并通过减小 j 来计算 i^j 直到到达 N，然后增加 i 等等。在多项式时间内求幂

例如如果 7776 < 8192 = 2^13，您尝试 2^12 = 4096，然后是 3^12、3^11、3^10、3^9、3^8，然后是 4^8、4^7、4^6 , 5^6, 5^5, 6^5 就完成了。

确定 N 是否为幂的多项式（以 n 为单位）时间算法

polynomial (in n) time algorithm that decides whether N is a power

algorithm

modulo