如何处理计算然后验证 10^8 个解决方案以找到一个真正的答案？

Question

我有一个长度为 615 位的号码。在整个数字中，有 8 个固定位置缺少数字。我必须找到那些丢失的数字是什么。所以有 10^8 种可能性。计算完它们后，我必须为每个可能的数字生成一个密文，然后查看输出是什么 (mod N)，然后查看哪个数字给出了正确的输出。换句话说，我试图在 RSA 问题中找到解密密钥。我现在主要关心的是如何 efficiently/properly 创建所有 10^8 个可能的答案。

我正在使用 gmpy2，为了让它工作，我必须下载 Python2.7，以免在尝试安装 gmpy2 时出现错误。我希望它们足以解决这个问题。如果没有，我真的很感激有人指出我正确的方向。

我还没有尝试过任何东西，因为我确信这需要几个小时来计算。所以我真的想确保我做的一切都是正确的，这样如果我让我的笔记本电脑运行几个小时，我不会弄乱内部，也不会冻结，我会坐在这里不知道是否我的笔记本电脑坏了，或者它还在计算。

所以我想我正在尝试就如何进一步进行寻求建议。

就实际代码而言，我想循环 0-9 8 次并不难，但我不知道如何将一个数字转换为另一个数字。在Python中，如何让一个数字只插入到我需要的位置？该数字类似于此示例：

X = 124621431523_13532535_62635292 //this is only 30 digits long, mine is 615 digits long

其中每个“_”都缺少一个数字。

我完全不知道该怎么做。

生成所有数字后，我的目标是遍历所有数字并提高它们，直到得到所需的答案。这部分似乎更容易一些，因为它看起来只是一个简单的循环。

所以我想我的主要问题是如何遍历 10^8 个数字，但将它们放在一个已经有 615 位数字的数字内的特定位置？我正在寻求有关技术和代码设计的建议，以免花费太长时间来生成它们。

感谢您的阅读。

Answer 1

把数字转成字符串，用format的方法，用itertools.product生成数字填空，再转回去

示例：

from itertools import product

def make_seed(n, replace_positions):
    seed = str(n)
    to_replace = [-1] + replace_positions
    substrings = [seed[start + 1:end] 
                  for start, end 
                  in zip(to_replace, to_replace[1:])] + [seed[to_replace[-1] + 1:]]
    return '{}'.join(substrings)

def make_number(seed):
    n = seed.count('{}')
    for numbers in product([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], repeat=n):
        yield int(seed.format(*numbers))


seed = make_seed(123456789, [3, 5, 7])
# seed = '123{}5{}7{}9'

for i in make_number(seed):
    print(i)

输出：

Answer 2

由于十进制数字只是 digit * pow(10, n) 的总和，您可以假设未知数字为零，并将其与数字乘积相加

#   124621431523_13532535_62635292 this is the original digit
x = 124621431523013532535062635292
positions = [8,17] # the missing digits are the 8th and 17th digits from the right

from itertools import product
trials = product(range(0,10), repeat=2)
for t in trials:
    x_prime = x
    for (digit, pos) in zip(t, positions):
        x_prime = x_prime + digit * pow(10, pos)
    print(x_prime) # do your checking here

输出：

124621431523013532535062635292
124621431523113532535062635292
124621431523213532535062635292
124621431523313532535062635292
...
etc

如何处理计算然后验证 10^8 个解决方案以找到一个真正的答案？

How to tackle calculating then verifying 10^8 solutions to find the one true answer?

python

gmpy