Ответ 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 и внимательно, алгоритм может иметь период 2 ^ 64

Реализация

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

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

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

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