algorithm - 如何描述用于计算公式的多项式时间算法？

Question

我需要一些帮助来描述用于计算的多项式时间算法:

(a^(b^c)) 模 p

其中 a、b 和 c 是整数，p 是质数。

我的第一个想法是做两个循环，乘以 (bb).. c 次，然后乘以 (aa) 那么多次。然后拿那个 mod p。

虽然这些术语让我感到困惑。多项式时间算法在一定次数的迭代后结束，对吗？不知道如何正确回答这个问题。非常感谢任何提示和建议。谢谢!

Answer 1

平方求幂确实是最优解的一部分。正如其他人已经指出的那样，您可以在 O(log c) 中为给定的 x 计算 b^c (mod x)。

其次，我们需要利用 p 是素数的优势。输入费马小定理:如果 p 是素数，则 a^p=a (mod p)。换句话说:a^(b^c) = a ^ ((b^c) mod (p-1)) (mod p)

复杂度:O(log c) 来计算第二部分，结果是 [0, p-1] 之间的数字；由于第二次求幂是独立的，因此整体复杂度为 O(log c) + O(log (p-1))