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

Question

предположим, у меня есть несколько чисел, которые образуют ряд, например: 652,328,1,254, и я хочу получить начальное число, которое, если я, например, сделаю

srand(my_seed);

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

Answer 1

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

Если алгоритм более сложный, это может быть невозможно.

Обратите внимание, что алгоритм, используемый в стандартной библиотеке C, не ограничен стандартом, поэтому разные платформы могут иметь разные реализации.

Answer 2

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

Answer 3

У вас не может быть ошибки, связанной вообще. Либо ваш алгоритм работает, либо нет. Причина этого в том, что разумная граница ошибки, очевидно, намного меньше, чем RAND_MAX. Это, в свою очередь, означает, что младшие биты не так случайны, как старшие биты. Но хороший PRNG гарантирует, что все биты одинаково случайны.

Рассмотрим этот медленный, но математически обоснованный пример алгоритма ГСЧ:

int rand() {
  state = AES_encrypt(state);
  return state % RAND_MAX;
}
void srand(int seed) {
  state = AES_encrypt(seed);
}

Если вы можете найти какую-либо существенную корреляцию между выходной последовательностью и предыдущим state, алгоритм AES следует считать нарушенным.

Answer 4

Проверьте этот вопрос .

Как говорит Джастин, можно вернуться к линейному конгруэнтному генератору (который часто встречается в реализациях * 1005), когда у вас есть последовательность сгенерированных чисел. Думаю, проблема в том, чтобы узнать, какое из предыдущих значений является исходным семенем ...