Обратимый псевдослучайный генератор последовательности
Я хотел бы, чтобы своего рода метод создал довольно длинную последовательность случайных чисел, которые я могу просмотреть назад и вперед. Как машина со "следующими" и "предыдущими" кнопками, которые дадут Вам случайные числа.
Что-то как 10-разрядное разрешение (т.е. положительные целые числа в диапазоне от 0 до 1 023) достаточно, и последовательность> 100k числа. Это для простого игрового приложения типа, мне не нужны случайность силы шифрования или что-либо, но я хочу, чтобы это чувствовало себя довольно случайным. Я имею ограниченный объем памяти в наличии, хотя, таким образом, я не могу только генерировать блок случайных данных и пройти их. Я должен получить числа в "интерактивное время" - я могу легко потратить некоторых мс, думающий о следующем числе, но не удобно намного больше, чем это. В конечном счете это будет работать на своего рода микроконтроллере, вероятно, просто Ардуино.
Я мог сделать это с простым линейным congruential генератором (LCG). Продвижения просты, для движения назад я должен был бы кэшировать новые числа и сохранить некоторые точки с промежутками, таким образом, я могу воссоздать последовательность оттуда.
Но возможно СУЩЕСТВУЕТ некоторый псевдослучайный генератор, который позволяет Вам идти и вперед и вперед? Должно быть возможно поднять трубку два линейных сдвиговых регистра обратной связи (LFSRs), чтобы насыпать различные направления, нет?
Или возможно я могу просто обойтись искажением индекса с помощью какой-то хеш-функции? Я собираюсь попробовать это сначала.
Какие-либо другие идеи?
4 ответа
Зашифруйте последовательность 1, 2, 3, ... любым шифром и любым ключом.
AES доступен практически во всех современных системах и работает молниеносно .
Использование действительно простого симметричного алгоритма шифрования - один из самых простых способов сделать это. Каждое случайное число формируется путем простого шифрования предыдущего с помощью некоторого фиксированного ключа, а чтобы вернуться назад, нужно просто расшифровать.
Вы можете посмотреть на RC4 - код на http://en.wikipedia.org/wiki/RC4. Вы можете использовать гораздо меньший график ключей, чтобы все это поместилось на arduino.
Вы также можете идти назад с помощью LCG, это просто другой LCG, использующий обратный множитель по модулю вместе с подходящим приращением.
Для небольших чисел можно просто использовать перебор для поиска обратного числа, в общем случае его можно вычислить с помощью расширенного алгоритма GCD.
Если только ваша игра не предназначена исключительно для развлечения, без каких-либо ставок, я бы выбрал что-то криптографически безопасное, например, предложенный другими подход AES. LCG и другие линейные генераторы случайных чисел не могут противостоять интеллектуальному противнику.
Хотя я согласен с @BlueRaja, что вы должны просто использовать AES в "режиме счетчика" со случайным или запуск по времени для вашей последовательности, AES может быть недоступен или невозможен в вашей встроенной ситуации.
Я нашел эту интересную статью , в которой обсуждается, как построить обратимый ГПСЧ; это всего 10 страниц и множество примеров кода. Попробуйте, если AES у вас не работает.