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

StackOverflow https://stackoverflow.com/questions/2145554

  •  23-09-2019
  •  | 
  •  

Вопрос

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

srand(my_seed);

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

Это было полезно?

Решение

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

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

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

Другие советы

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top