algorithm - RSA算法复杂度分析

Question

RSA 的安全性取决于一个简单的假设:

Given N, e, and y = (x ^e) mod N, it is computationally intractable to determine x.

这个假设很合理。 Eve 会如何尝试猜测 x？

她可以尝试所有可能的 x 值，每次检查 x^e 是否等于 y mod N，但这将花费指数时间。或者她可以尝试分解 N 以检索 p 和 q，然后通过反转 e 模 (p-1)(q-1) 来计算 d，但我们认为分解很难。固执通常是沮丧的根源； RSA 的洞察力在于利用它来发挥优势。

我对上面文字的问题

1. 在上述情况下，我们如何获得用于计算每个 x 值的指数时间？

Answer 1

https://en.wikipedia.org/wiki/Time_complexity

...the time complexity is generally expressed as a function of the size of the input

此任务的输入大小与 b = N 中的位数成正比。因此，x 的所有可能值的迭代具有指数级的时间复杂度 O(2^b)。

在输入的数值方面具有多项式时间复杂度的算法称为pseudo-polynomial algorithms .例如，众所周知 integer factorization problem没有已知的多项式算法。但我们可以简单地从 2 迭代到 sqrt(N) 并在 O(sqrt(N) 中找到数字 N 的所有质因数)) 时间。此算法在N方面具有多项式复杂度，但此问题的输入长度不是N，而是log(N) 大约。因此，本次迭代只是一个伪多项式解。