Блог

У меня есть число длиной 615 цифр. Во всем числе есть 8 фиксированных мест, где отсутствует цифра. Я должен найти, что это за недостающие цифры. Итак, существует 10 ^ 8 возможностей. После их вычисления я должен создать шифротекст для каждого возможного числа и посмотреть, каков результат (mod N), и посмотреть, какое число дает правильный результат. Другими словами, я пытаюсь найти ключ дешифрования в задаче RSA. Моя главная задача сейчас — как эффективно / правильно создать все 10 ^ 8 возможных ответов.

Я использую gmpy2, и чтобы заставить это работать, мне пришлось загрузить Python2.7, чтобы не получить ошибку при попытке установить gmpy2. Я надеюсь, что они достаточно адекватны для решения этой проблемы. Если нет, я был бы очень признателен, если бы кто-нибудь указал мне правильное направление.

Я еще ничего не пробовал, так как уверен, что на вычисления уйдут часы. Поэтому я действительно хочу убедиться, что я все делаю правильно, чтобы, если я позволю своему ноутбуку работать пару часов, я не испортил внутренности, и он не зависнет, и я буду сидеть здесь, не зная, испортился ли мой ноутбук, или он все еще вычисляет.

Итак, я полагаю, я пытаюсь получить совет о том, как мне действовать дальше.

С точки зрения фактического кода, я полагаю, что повторение 0-9 8 раз не так сложно, но я не знаю, как преобразовать число в другое число. Как мне сделать так, чтобы число вставлялось только в ту позицию, в которой оно мне нужно? Число выглядит следующим образом:

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

где каждое «_» — это то, где отсутствует число.

Я совершенно не понимаю, как это сделать.

Как только все числа сгенерированы, я намерен перебирать их все и увеличивать их, пока не получу требуемый ответ. Эта часть кажется немного проще, так как кажется, что это просто простой цикл.

Итак, я предполагаю, что мой главный вопрос заключается в том, как перебирать 10 ^ 8 чисел, но помещать их в определенное место внутри числа, длина которого уже составляет 615 цифр? Я ищу совета как по техническому, так и по дизайну кода, чтобы не занимать слишком много времени для их создания.

Спасибо за чтение.

Превратите число в строку, используйте 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)
  

Вывод:

 123050709
123050719
123050729
123050739
123050749
123050759
123050769
123050779
123050789
123050799
123051709
123051719
123051729
...
  

Поскольку десятичная цифра — это просто суммирование 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