Зададох много подобен въпрос във форумите на 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

Внедряване

Направих имплементация само за заглавка на този алгоритъм, в случай че някой се интересува.

Използването на наистина прост алгоритъм за симетрично криптиране е един от най-лесните начини да направите това. Всяко произволно число се формира чрез просто криптиране на предишното с някакъв фиксиран ключ и за да се върнете назад, просто дешифрирате.

Може да погледнете 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 дават желаните резултати. В случай, че не можете да решите упражнението, можете лесно да намерите решения за него, напр. тук

Въпреки че съм съгласен с @BlueRaja, че трябва просто да използвате AES в „режим на брояч“, с произволно или базирано на време начало за вашата последователност, AES може да не е наличен или осъществим във вашата вградена ситуация.

Намерих този интересен документ, който обсъжда как да изграждане на обратим PRNG; има само 10 страници и има много примерни кодове. Дайте го като опитате, ако AES не работи за вас.

Можете също да се върнете назад с LCG, това е просто друг LCG, използващ обратното на множителя по модула, заедно с подходящо увеличение.

За вашите малки числа можете просто да използвате груба сила, за да търсите обратното, като цяло може да се изчисли с разширен GCD алгоритъм.

Освен ако играта ви не е само за забавление, без никакви залози от какъвто и да е вид, бих избрал нещо криптографски сигурно, като подхода AES, предложен от други. LCG и други линейни генератори на случайни числа не могат да устоят на интелигентен противник.