RSA的安全性取决于一个简单的假设：
给定N，e和y =（x ^ e）mod N，确定x在计算上是难以处理的。
这个假设很合理。夏娃怎么会试着猜x？
她可以尝试x的所有可能值，每次检查x ^ e是否等于y mod N，但这需要指数时间。或者她可以尝试将N因子检索到p和q，然后通过反转e modulo（p-1）（q-1）来计算d，但我们认为因子分解很难。难以理解通常是令人沮丧的根源; RSA的洞察力在于利用它。
我对上述文字的质疑
https://en.wikipedia.org/wiki/Time_complexity
...时间复杂度通常表示为输入大小的函数
此任务的输入大小与b = N中的位数成比例。因此，通过x的所有可能值的迭代具有指数的时间复杂度O(2^b)。
根据输入的数值具有多项式时间复杂度的算法称为pseudo-polynomial algorithms。例如，众所周知，integer factorization problem没有已知的多项式算法。但我们可以简单地从2迭代到sqrt(N)，并在N时间找到O(sqrt(N))数的所有素因子。该算法具有N的多项式复杂度，但该问题的输入长度不是N，它大约是log(N)。结果，该迭代仅是伪多项式解。