algorithm - 'Polynomial in number of bits in the input' 是什么意思？

Question

所以我有一个类(class)作业是问一个关于复杂性理论的问题，我有一些问题，PRIMES，它在 NPTime 复杂性类中。

到目前为止一切都很好。

让我头疼的是一个计算 (a^p)mod(b) 的多项式时间算法的问题。它必须是输入大小(位数)的多项式。

让我感到困惑的是后一句话。

这就是它失去我的地方!当然，假设暴力尝试(2 和 sqrt(n) 之间的所有值)，会给出 2^NoBits，这是指数？!

现在我不要答案了!这是我的类(class)作业，所以我不能要求。我只想弄清楚“输入位数的多项式”是什么意思。像对 child 一样解释它；)

Answer 1

您有 3 个数字，a、p 和 b。每一个都可以是任何尺寸。 1. 10. 123_456_789。没有限制。

当我们以 2 为基数编写它们时，每个都是一些位数，后面跟着那串位。所以 1、110、111010110111100110100010101。每个都是一些位数。 1, 2, 27. 位数之和就是你输入的总大小。 30.

您的算法应该足够高效，存在一些多项式 p(x)，其中 x 是输入中位数的总和，它是一个上取决于您的计算需要多长时间。

特别注意，您不想将 a 乘以 p 次!