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

Question

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

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

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

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

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

Есть еще идеи?

Answer 1

Я задал очень похожий вопрос на форумах 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 и a, алгоритм может иметь период 2 ^ 64

Осуществление

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

• 0 <=> 0
• 1 <=> 128
• 2 <=> 64
• 3 <=> 192
• 4 <=> 32
• и т.д.

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

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

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

Answer 5

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

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

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

Answer 6

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

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

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

Answer 7

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

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