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

Question

我是一名计算机科学专业的学生；我正在独立学习算法课程。

\n

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

\n

\n

给定一个n位整数N，找到一个多项式（n）时间算法来决定N是否为幂（即，存在整数a和k> 1，使得a^k = N）。

\n

\n

我想到了第一个选项，它是 n 的指数：\n对于所有 k ， 1<k<N ，尝试将 N 除以 k 直到得到结果 1。

\n

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

\n

我的第二个选择是使用模算术，如果 gcd(a, k+1 ) = 1 （欧拉定理），则使用^{k \xe2\x89\xa1 1 mod (k+1) 。}我不知道a和k是否互质。

\n

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

\n

function power(N)\nInput: Positive integer N\nOutput: yes/no\nPick positive integers a_1, a_2, . . . , a_k < N at random\nif (a_i)^N\xe2\x88\x921 \xe2\x89\xa1 1 (mod N)\nfor all i = 1, 2, . . . , k:\n    return yes\nelse:\n    return no\n

\n

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

\n

Answer 1

忽略 N 为 0 或 1 的情况，您想知道 N 是否可以表示为 a^b（对于 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 的多项式。