algorithm - 使用预言机有效地对整数进行质因数分解

Question

假设您有一个程序 one_factor(N)，给定一个 n 位二进制数 N，它返回质数之一Theta(n^2) 时间中数字的因子(请注意，我在 theta 表示法中使用了小写的 n。)

使用这个算法，我想找到一种有效的算法来将 n 位二进制数分解为素数并打印素数因子。此外，我想知道算法作为 n 的函数运行有多快，并且我还想计算我的算法使用 one_factor(N) 的大致次数oracle 在最坏的情况下作为 n 的函数。

假设两个 n 位二进制数的加/除/乘/减需要 Theta(n) 时间。

---

这是一个有效的算法:

• 调用one_factor(N)。如果函数返回 N，则 N 是素数，我们就完成了。否则，将这个质因数除掉并将其存储在某个地方。重复此过程，直到完成。

现在我无法将此过程的运行时分析为 n 的函数。为简单起见，如果 N 是 2 的幂，则 n = log_2(N)，但我不太确定如何从这里继续。

我不明白如何找到我们调用 one_factor 的最坏情况次数，而且我在分析最坏情况运行时间时也遇到了麻烦。

Answer 1

首先，预言机很棒，但速度很慢。所以你想先尝试进行试除。

来自Arithmetic functions in Wikipedia如果您使用 Newton–Raphson 除法和 Harvey-Hoeven 算法，则可以在 O(n log(n)) 时间内完成检查是否能被素数 p 整除>。使用远小于 O(n^2)< 的埃拉托斯特尼筛筛时间，可以计算 O(n/log(n)) 素数直至 n/。进行试除法可以在 O(n^2) 时间内完成。 (使用更实用的乘法算法，您可以在稍微差一点的时间内完成它。这不会对整体结果产生影响。)

现在你引用你的预言机。每个预言机都需要时间O(n^2)，并且与此相比，划分很小。它将数字的大小减少至少 n 倍。需要如何划分？ O(log_n(2^n)) = O(log(2^n)/log(n)) = O(n/log(n))。按照与上述相同的算法，每个除法都是O(n log(n))。

生成的算法为O(n^2 * (n * log(n)) * n/log(n)) = O(n^4)。请注意，/log(n) 是在咨询预言机之前进行试除所节省的费用。

请注意，您无法通过进行更多的试除法来改进这一点，因为如果您尝试遍历直到 n^2 的所有素数，您在试除法上花费的时间比原始算法要多，并且预言机部门的大O仍然是一样的。