Найти начальное число, которое создает определенную c числовую последовательность с random.choice (range (128))?

Question

Я хочу найти начальное число, которое создает определенную c числовую последовательность:

[115,91,45,76,78,93,35,5,29,8,99,88,98,70,40,116,11,39,102,41,124,98,120,57,36,67,57,23,52,34,75,32,117,66,12,19,86,67,62,121,60,5,54,37,65,18,5,56,66,115,32,99,73,70,115,73,123,74,31]

Интересно, смогу ли я найти одно из начальных чисел, которое даст мне этот результат, с помощью функции get (), которую я создал :

def get():
   seed(x)
   return [choice(range(128)) for _ in range(59)]

с константой x, равной числу, которое, применяя в качестве семени, дает мне правую верхнюю последовательность сверху.

Это небольшая программа, которую я сделал, чтобы найти ее, но прямо сейчас я проверил семена примерно на 1,6 миллиона, а еще ничего.

from random import choice, seed

lc =[115,91,45,76,78,93,35,5,29,8,99,88,98,70,40,116,11,39,102,41,124,98,120,57,36,67,57,23,52,34,75,32,117,66,12,19,86,67,62,121,60,5,54,37,65,18,5,56,66,115,32,99,73,70,115,73,123,74,31]

sd, h = 0,0
while 1:
  seed(sd)
  for c, o in enumerate(lc):
    if not choice(range(128)) == o:
      if c > h :
        print(f"[Seeed {sd}] {c} matchs")
        h = c
      sd += 1
      break

Может ли кто-нибудь помочь мне найти одно правильное семя?

Answer 1

Я надеюсь, что это невозможно. Технически, можно кодировать квазислучайный генератор, который позволяет восстановить начальное число с помощью короткой последовательности результатов. Но обычный квазислучайный генератор должен это запретить. Например, для довольно распространенного Mersenne Twister внутреннее состояние составляет 624 дюйма. Но твое семя всего лишь одно целое. Даже если вы перебираете семя, которое дает вам ту же самую короткую последовательность, фактическое внутреннее состояние может отличаться, и последующее поколение будет идти совершенно другим путем.

Answer 2

Любой отобранный PRNG будет иметь формулу для генерирования следующего числа из внутренних данных, которые он хранит. С помощью чего-то простого, например, линейного конгруэнтного PRNG, можно легко произвести обратный расчет внутренних данных и чисел, используемых в формуле, из выходных данных. С более сложным PRNG, таким как Mersenne Twister, обратный расчет становится очень трудным.

Одним из решений было бы скопировать нужную последовательность чисел и сохранить их где-нибудь, вытаскивая их из магазина по мере необходимости. , В качестве альтернативы прочтите документацию PRNG, использованную для первоначального генерирования этих чисел, чтобы увидеть, возможен ли обратный расчет.

Если числа получены из криптографически безопасного PRNG, тогда ваша задача становится на несколько порядков сложнее.

Answer 3

Используя грубую силу и предполагая, что каждое семя представляет собой извлечение из вашего набора чисел (128), с заменой у вас есть вероятность

1/(128)^59 = 1 / 2.1153791001287955166461289857048673274508949854856999 × 10^124

для каждого извлечения, чтобы получить ваш точный набор чисел (при условии равномерного распределения для каждого извлечения числа вашей случайной функции). Что является вероятностью, близкой к нулю.

Так что да. Вы можете повесить (почти) навсегда для этого поиска грубой силы