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

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

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

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

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

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

Любые другие идеи?


random arduino reverse prng
person PapaFreud    schedule 26.05.2010    source источник

Ответы (7)


arrow_upward
25
arrow_downward

Я задал очень похожий вопрос на форумах 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.

Реализация

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

person bobbaluba    schedule 19.05.2013
comment
спасибо @bobbaluba - я нашел эту информацию очень полезной. Я не очень хорошо разбираюсь в математике, поэтому я попытался создать небольшое руководство по обращению модульных функций на случай, если кто-то вроде меня столкнется с этим в будущем: stackoverflow.com/questions/29569927/ - person Jonathan Basile; 13.04.2015
comment
У меня сложилось впечатление, что хеширование последовательных целых чисел приведет к субслучайным последовательностям. См. stackoverflow.com/a/41728178/225186. - person alfC; 09.12.2017
comment
Спасибо @bobbaluba за то, что поделились кодом. Я только что попытался выполнить его, и расчет шага назад занимает около 1,4 секунды по сравнению с практически мгновенным шагом вперед. Это правда или я что-то не так делаю? Я предполагаю, что это расширенный алгоритм Евклида, который занимает так много времени обработки, не так ли? - person Bill; 02.01.2021
comment
@Bill: Может быть, вы компилируете с отключенной оптимизацией? ainverse является результатом функции constexpr, выполняемой с постоянными параметрами, большинство компиляторов должны быть достаточно умны, чтобы предварительно вычислить это, если оптимизация включена (в примерах я использую g++ с -O2, что делает для меня мгновенным). В любом случае, я увеличил требование в репозитории выше до C++17, что позволяет использовать переменные constexpr, которые, как я думаю, должны обеспечивать вычисление времени компиляции также в режиме отладки. - person bobbaluba; 03.01.2021

arrow_upward
11
arrow_downward

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

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

person Cullen Fluffy Jennings    schedule 28.05.2010

arrow_upward
6
arrow_downward

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

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

person BlueRaja - Danny Pflughoeft    schedule 28.05.2010

arrow_upward
2
arrow_downward

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

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

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

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

График рассеяния случайно сгенерированных значений

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

person Matt Thomas    schedule 18.01.2017
comment
У меня нет математического доказательства, но результирующая последовательность выглядит как субслучайная. en.wikipedia.org/wiki/Low-discrepancy_sequence. Тем не менее может быть полезен во многих приложениях. - person alfC; 08.12.2017
comment
@alfC Моя картинка определенно похожа на набор Хаммерсли, и Вольфрам говорит, что вы можете сгенерировать этот набор, поменяв порядок битов на обратный. Я думаю, это доказательство того, что вы правильно. Спасибо за ссылку! - person Matt Thomas; 08.12.2017
comment
Точно, ведь даже если бы она была случайной, она была бы более чем обратимой/двунаправленной, это была бы случайная последовательность со случайным доступом. Мне всегда было интересно, существует ли такая вещь. То есть пропустить N случайных чисел (в любом направлении) за O(1). - person alfC; 08.12.2017
comment
@alfC Если все, что вам нужно, это O (1) генерация i-го числа в псевдослучайной последовательности, и вас не волнует ее обратимость, то r (i, seed) = hash (i + seed) поможет; просто выберите свою любимую хеш-функцию - person Matt Thomas; 09.12.2017
comment
Да, но это будет субслучайно, а не случайно. Я не сомневаюсь в том, что подслучайный доступ - это произвольный доступ (переходы O (1)). У меня вопрос, есть ли случайные последовательности с произвольным доступом. - person alfC; 09.12.2017
comment
@alfC Я не понимаю, как хэш (i + seed) создает последовательность с низким расхождением (с соответствующей хеш-функцией, например, SHA256)? - person Matt Thomas; 11.12.2017
comment
И я нет. Это интуиция, если бы случайное число могло быть сгенерировано таким образом, оно не требовало бы памяти, и это было бы странно. Если бы это не было субслучайным, это был бы плохой хэш. Мой вывод состоит в том, что хэши создают субслучайные последовательности при применении к программным последовательностям. - person alfC; 11.12.2017
comment
@alfC Позвольте мне повторить более уверенно: Криптографически безопасный хэш счетчика также может послужить хорошей CSPRNG в некоторых случаях (CSPRNG = криптографически безопасный генератор псевдослучайных чисел). Обратите внимание, что чаще используется функция шифрования вместо хеш-функции, но принцип тот же. - person Matt Thomas; 11.12.2017
comment
@alfC Возможно, это поможет интуиции: обычно легко преобразовать внутреннее состояние функции в параметр. Другими словами, в функции, имеющей внутреннее состояние, нет ничего волшебного. В случае использования функции хеширования/шифрования для выполнения PRNG все необходимое состояние инкапсулируется в эти два параметра (i и seed). Точно так же вы можете реорганизовать свою любимую функцию PRNG, чтобы все состояния поступали в виде параметров, а из нее возвращались все описания побочных эффектов. - person Matt Thomas; 11.12.2017
comment
@alfC В качестве игрушечного примера для моего предыдущего комментария , рассмотрите этот линейный конгруэнтный генератор (PRNG): {int seed = 1337; int rand() { seed = (4321 * seed + 2345) % 53; return seed; }. Эта функция делает то же самое: int rand(int seed) { return (4321 * seed + 2345) % 53; } - person Matt Thomas; 11.12.2017
comment
они будут делать то же самое, если семя хранится. А это значит, что легких прыжков не бывает. Другими словами, for(int i = 0; i != 1000; ++i) print(rand()); и for(int i = 0; i != 1000; ++i) print(rand(i)); не будут делать одно и то же. Я бы сказал, что первое является случайным (то есть квазислучайным), а второе — субслучайным. Ты согласен? - person alfC; 11.12.2017
comment
@alfC См. мой ответ в chat.stackoverflow.com/transcript/160976 (у вас есть доступ для редактирования) - person Matt Thomas; 12.12.2017

arrow_upward
2
arrow_downward

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

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

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

person Udo Klein    schedule 02.05.2017

arrow_upward
0
arrow_downward

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

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

person Randolpho    schedule 28.05.2010

arrow_upward
0
arrow_downward

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

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

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

person starblue    schedule 29.05.2010