Как решить вычисление, а затем проверить 10 ^ 8 решений, чтобы найти один верный ответ? - PullRequest
Новая
       39

Как решить вычисление, а затем проверить 10 ^ 8 решений, чтобы найти один верный ответ?

3 голосов
/ 10 апреля 2019

У меня есть номер длиной 615 цифр.Во всем номере 8 фиксированных мест, где не хватает цифры.Я должен найти, что это за пропущенные цифры.Так что есть 10 ^ 8 возможностей.После их вычисления я должен поднять зашифрованный текст до каждого возможного числа и посмотреть, что это за выход (мод N), и посмотреть, какое число дает правильный вывод.Другими словами, я пытаюсь найти ключ дешифрования в проблеме RSA.Моя главная задача сейчас - как эффективно / правильно создать все 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 цифр?Я ищу советы как по технической разработке, так и по дизайну кода, чтобы их создание не заняло слишком много времени.

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

Ответы [ 2 ]

2 голосов
/ 10 апреля 2019

Превратите число в строку, используйте метод 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
...
1 голос
/ 10 апреля 2019

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