'Polynomial in number of bits in the input' 是什么意思？
What is meant by 'Polynomial in number of bits in the input'?
所以我有一个课程作业是问一个关于复杂性理论的问题，我遇到了一些问题，PRIMES，它在 NPTime 复杂性中 class。
到目前为止一切都很好。
让我头疼的问题是提出用于计算 (a^p)mod(b) 的多项式时间算法。它必须是输入大小（位数）的多项式。
是后一句让我很困惑
这就是我迷路的地方！当然，假设暴力尝试（2 和 sqrt(n) 之间的所有值），将给出 2^NoBits，这是指数？！
现在我不要答案了！这是我的课程作业，所以我不能要求。我只想弄清楚 'polynomial in the number of input bits' 的含义。像对 child ;)
一样解释它
您有 3 个号码，a、p 和 b。每一个都可以是任何尺寸。 1. 10. 123_456_789。没有限制。
当我们以 2 为基数编写它们时，每个都是一些位数，然后是该串位。所以 1、110、111010110111100110100010101。每个都是一些位数。 1, 2, 27. 位数之和就是你输入的总大小。 30.
你的算法应该足够高效，以至于有一些多项式 p(x) 其中 x 是输入中位数的总和，这是你的计算将持续多长时间的上限
特别注意，您不想将 a 乘以 p 次！
所以我有一个课程作业是问一个关于复杂性理论的问题，我遇到了一些问题，PRIMES，它在 NPTime 复杂性中 class。
到目前为止一切都很好。
让我头疼的问题是提出用于计算 (a^p)mod(b) 的多项式时间算法。它必须是输入大小（位数）的多项式。
是后一句让我很困惑
这就是我迷路的地方！当然，假设暴力尝试（2 和 sqrt(n) 之间的所有值），将给出 2^NoBits，这是指数？！
现在我不要答案了！这是我的课程作业，所以我不能要求。我只想弄清楚 'polynomial in the number of input bits' 的含义。像对 child ;)
一样解释它您有 3 个号码，a、p 和 b。每一个都可以是任何尺寸。 1. 10. 123_456_789。没有限制。
当我们以 2 为基数编写它们时，每个都是一些位数，然后是该串位。所以 1、110、111010110111100110100010101。每个都是一些位数。 1, 2, 27. 位数之和就是你输入的总大小。 30.
你的算法应该足够高效，以至于有一些多项式 p(x) 其中 x 是输入中位数的总和，这是你的计算将持续多长时间的上限
特别注意，您不想将 a 乘以 p 次！