Обратимый генератор псевдослучайных последовательностей

Я хотел бы, чтобы какой-то метод создал довольно длинную последовательность случайных чисел, которую я мог бы пролистывать взад и вперед. Как машина с кнопками "следующий" и "предыдущий", которая даст вам случайные числа.

Достаточно что-то вроде 10-битного разрешения (т.е. положительных целых чисел в диапазоне от 0 до 1023) и последовательности из>100k чисел. Это для простого игрового приложения, мне не нужна случайность с шифрованием или что -то в этом роде, но я хочу, чтобы оно казалось случайным. У меня ограниченный объем доступной памяти, поэтому я не могу просто сгенерировать кусок случайных данных и просмотреть их. Мне нужно получить числа в "интерактивном времени" - я могу легко потратить несколько мс, думая о следующем числе, но не намного удобнее, чем это. В конце концов он будет работать на каком-то микроконтроллере, возможно, просто на Arduino.

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

Но, может быть, есть какой-то псевдослучайный генератор, который позволяет вам идти вперед и назад? Должна быть возможность подключения двух регистров сдвига с линейной обратной связью (LFSR) для вращения в разные стороны, не так ли?

Или, может быть, я могу просто обойтись с искажением номера индекса с помощью некоторой хэш-функции? Я собираюсь попробовать это в первую очередь.

Есть другие идеи?

Источник

7 ответов

Решение

Я задал очень похожий вопрос на форумах Tigsource.

хеширования

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

class ReversibleRNG {
    int x;
public:
    ReversibleRNG(int seed) : x(seed) {}
    int next(){return yourFavoriteHash(++x);}
    int prev(){return yourFavoriteHash(--x);}
};

Обратимый линейный конгруэнтный генератор (lcg)

Как указали несколько людей, lcg действительно обратим. В lcg следующее состояние вычисляется так:

x = (a * prevx + c) mod m

Мы можем изменить порядок этого:

x ≡ a * prevx + c (mod m)
x - c ≡ a * prevx (mod m)

Поскольку a и m выбираются относительно простыми в lcg, мы можем найти обратное с помощью расширенного алгоритма Евклида.

ainverse = extEuclid(a, m).x;
ainverse * (x - c) ≡ ainverse * a * prevx (mod m)
ainverse * (x - c) ≡ prevx (mod m)

Что значит

prevx = ainverse * (x - c) mod m

Если вы выбираете m и тщательно, алгоритм может иметь период 2^64

Реализация

Я сделал реализацию этого алгоритма только на заголовке на случай, если кому-то будет интересно.

Источник

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

Вы можете посмотреть код RC4 по адресу http://en.wikipedia.org/wiki/RC4. Вы могли бы использовать намного меньший ключевой график, чтобы все это поместилось на Arduino.

Источник

Зашифровать последовательность 1, 2, 3, ... с любым шифром и любым ключом.

AES доступна практически на всех последних системах и работает молниеносно.

Источник

Просто измените порядок битов в возрастающей последовательности целых чисел. Например (с разрешением 8 бит):

  • 0 <=> 0
  • 1 <=> 128
  • 2 <=> 64
  • 3 <=> 192
  • 4 <=> 32
  • так далее

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

Это определенно не криптографически безопасно. Вот график рассеяния сгенерированных значений (опять же с разрешением 8 бит):

Точечный график

Вы можете легко увидеть шаблоны, хотя это может быть "случайным" для вас достаточно.

Источник

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

Подробности можно найти в "Искусство компьютерного программирования", том 2

В частности, раздел 3.2.1 Уравнения 6-8 TAOCP, а также упражнение 5 дают желаемые результаты. Если вы не можете решить упражнение, вы можете легко найти решение, например, здесь

Источник

Вы также можете вернуться назад с помощью LCG, это просто еще один LCG, использующий обратное значение множителя по модулю вместе с подходящим приращением.

Для ваших небольших чисел вы можете просто использовать грубую силу для поиска обратного, в общем случае его можно вычислить с помощью расширенного алгоритма GCD.

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

Источник

Хотя я согласен с @BlueRaja, что вы должны просто использовать AES в "режиме счетчика", при случайном или временном запуске вашей последовательности AES может быть недоступен или неосуществим в вашей встроенной ситуации.

Я нашел эту интересную статью, в которой обсуждается, как построить обратимый PRNG; это всего 10 страниц и имеет множество примеров кода. Дайте это при попытке, если AES не работает для вас.

Источник
Другие вопросы по тегам