Попытка написать обратимый PRNG из 8 бит, а не шифр - PullRequest
Новая
       43

Попытка написать обратимый PRNG из 8 бит, а не шифр

1 голос
/ 10 января 2012

Я пытаюсь построить PRNG байтов, где я могу взять набор байтов (скажем, 10 или 15 байтов) и вернуть список начальных значений, который бы вывел этот список байтов.Я не беспокоюсь о криптографии, но она должна быть примерно равномерно распределена, она должна охватывать все возможные комбинации 2 ^ 8 и иногда должна иметь возможность повторять число без застревания.

Проблема в том, что большинствоАлгоритмы, о которых я читал, либо используют шифры, что, вероятно, означает, что они не допускают повторов, либо используют модули или некруглые сдвиги, которые вызывают потери и делают реверсирование функции в лучшем случае нецелесообразным.Кроме того, если бы алгоритм использовал подсчет, было бы трудно работать в обратном направлении, поскольку входной список байтов не знал бы, какой был внутренний счетчик PRNG во время генерации.

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

Во время поиска я наткнулся на этот пост который имеет аналогичные требования.Я писал на C #, но на самом деле синтаксис не важен.

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

Ответы [ 2 ]

1 голос
/ 13 января 2012

Это работает?

#include <stdio.h>

int seed = 1;

int next() {
    seed = 1664525*seed + 1013904223;
    return (seed & 0xff) ^ (seed>>8 & 0xff) ^ (seed>>16 & 0xff) ^ (seed>>24 & 0xff);
}   

int main() {
    int i;
    for(i = 0; i < 1000; i++) {
        printf("%d\n", next());
    }   
}

Поскольку он основан на линейном конгруэнтном генераторе (LCG) с полным периодом, каждый байт, в конце концов, будет генерироваться каждым начальным числом.Там, кажется, повторяется.И он наследует однородность базового LCG.

0 голосов
/ 22 января 2013

Мой советник изменил PRNG (основанный на clcg4 от L'Ecuyer), чтобы быть обратимым для поддержки усилий по моделированию HPC нашей группы.Вы можете прочитать об этих здесь .

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

...