Как справиться с вычислением, а затем проверкой 10 ^ 8 решений, чтобы найти единственный верный ответ?
У меня есть номер длиной 615 цифр. Во всем номере есть 8 фиксированных мест, где пропущена цифра. Я должен найти, что это за пропущенные цифры. Таким образом, есть 10 ^ 8 возможностей. После их вычисления я должен поднять зашифрованный текст до каждого возможного числа и посмотреть, каков результат (mod 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 цифр? Я ищу совета по техническим вопросам, а также по дизайну кода, чтобы не тратить слишком много времени на их генерацию.
Спасибо за чтение.
Суть в том, что x**(a+b) mod N можно разложить на x**a * x**b mod N, поэтому вам нужно сделать только один с нулями, который является a, а затем выполнить некоторую работу для каждого из bs.
Ответы 2
Превратите число в строку, используйте метод 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
...
Спасибо. Как вы думаете, сколько времени потребуется для получения числа, состоящего из 615 цифр и в котором отсутствуют 8 цифр?
На генерировать номера? Наверное, не меньше часа.
Могу я спросить, почему вы подчеркнули «генерировать»? Как вы думаете, сколько времени потребуется на генерацию, проверку и переход к следующему числу?
Могу я спросить, как бы вы изменили это, чтобы я мог запускать его в разных точках? например сгенерировать число от 0 до 10 000 000, а затем другое от 10 000 000 до 20 000 000, чтобы я мог запускать их одновременно? На данный момент бег от 0 до 100 000 000 займет у меня несколько дней.
О времени работы: меня это бьет, но вы, вероятно, могли бы сделать простое профилирование времени. О запуске: я полагаю, вы могли бы назначить генератор переменной и использовать другой цикл с yield from?
Поскольку десятичная цифра — это просто сумма 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
да, это будет repeat=8. По сути, product должен дать вам поток десятичных цифр длины N, где N — количество пропущенных цифр.
Если бы я изменил это на 8 неизвестных, изменил бы я «повтор = 2» на «повтор = 8»? Я также изменил оператор печати на оператор if, который напечатает число, а затем сломается. Я запускаю это с этими поправками прямо сейчас, и это было 2 часа. Есть ли другие поправки на 8 неизвестных?
Кстати, обратите внимание, что это похоже на очень наивный подход к перечислению. Может быть более оптимизированный подход, который не требует перечисления всего пространства ответов 10 ^ 8.
Знаете ли вы, в какой момент номер «отсутствует». Если вы это сделаете, вы можете предположить, что эти цифры равны нулю. Затем создайте массив
arrдлины 8. N-й элемент массива — это число от 0 до 9, которое вы хотите проверить на N-й цифре. Если N-я цифра находится в позиции M, то X = X + 10^M, где M считается как 0, начиная с младшей значащей цифры. Затем вам нужно сгенерировать все возможные перестановки arr, перебрать их и проверить, решает ли он шифр.