有没有可能通过10^8种可能性来确定正确答案？

Question

我有一个615位数的数字。在这本书中，有8处数字缺失。我得找出数字是什么。有10^8种可能性。你知道吗

这是一个RSA问题。有问题的数字是私钥，我正试图找出它是什么。为了帮助我，我有一个公钥对（n，e），两个都是615位数字长，还有一个明文和相应的密文。你知道吗

所以找出d的唯一方法就是用力。我试图在python中使用gmpy2来解决这个问题。我得克服重重困难才能使它发挥作用。我甚至不知道我做得对不对。我不得不下载Python2.7，这样我就可以运行gmpy2安装程序而不会得到错误消息。但我想现在可以了，因为我可以打字了

>>>import gmpy2

在终端，它不会给我一个错误。你知道吗

在我尝试循环10^8种可能性之前，考虑到我的情况，我想知道是否有可能在相对较短的时间内这样做。我不想炒我的电脑或冻结它试图计算这个。我还想知道我是否为此使用了正确的工具，或者gmpy2不是正确的版本，或者Python2.7不够好/快。我正在笔记本电脑上运行Python2.7上的gmpy2。你知道吗

最后，我想我要把所有的10^8个答案加起来，使C^d=M mod n，这是一个（已经）很大的数，等于615位数的幂，10^8倍。这可能吗？如果是，我如何使用gmpy2实现这一点？有没有更有效的方法来计算这个？你知道吗

我真诚的道歉，如果这不是正确的地方问这个问题。谢谢你的帮助。你知道吗

Answer 1

我是维护者。你知道吗

要计算C**d mod n，应该使用内置的pow()并指定所有三个值。pow(C,d,n)将比C**d % n快得多。你知道吗

使用gmpy2应该很容易做到这一点。与使用int()将字符串转换为Python整数不同，您只需要使用gmpy2.mpz()。您可以将pow()与mpz实例一起使用。（如果pow()的三个值中有一个是mpz，则gmpy2将用于计算。）

我用gmpy2估计运行时间从不到一个小时到几个小时不等。Python的本机整数可能慢10倍。你知道吗