Ищете альтернативный алгоритм PRNG с возможностью повторного использования/без атак

Question

Я ищу генератор псевдослучайных чисел, который является «воспроизводимым» и «без гражданства». Позвольте мне уточнить: мне нужно иметь возможность повторно получать псевдослучайное число, основанное на параметре, на случайную функцию. Например (C-стиль псевдокод):

int x1 = random(1); 
int x2 = random(2); 
// and so on with lots of random() calls in between 
int new_x1 = random(1); 
// now new_x1 is like a "replay" of x1, so x1 == new_x1 

тип аргументов не имеет значения (я могу типаж все, что необходимо), возвращаемое значение не должно быть int; в конечном итоге мне понадобятся 8-битные значения.

Вопрос в том, что хороший алгоритм PRNG, который удовлетворяет требованию о том, что следующее псевдослучайное значение контролируется параметром, а не его внутренним состоянием, которое обновляется при каждом вызове? Я не то, что использовать вшивое решение, как следующее:

int random(int input) { 
    srand(input); 
    return rand(); 
} 

Это было бы инициализировать PRNG при каждом вызове, который, кажется дорогостоящим. (Я иллюстрирую этот момент, используя стандарт srand()/rand(), я знаю, что там есть лучшие алгоритмы, такие как Mersenne Twister, но идея все та же.)

Answer 1

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

int pseudorandomValue(int input) { 
    return encryptUsingAES(input); 
} 

Это не зависит от состояния, псевдослучайной (так как выходы AES должны быть статистически неотличимы от случайных), и лиц без.

Надеюсь, это поможет!

Answer 2

Вы можете использовать PRNG на основе Xorshift [1,2]. Этот PRNG использует предыдущее случайное число для генерации следующего. Реализация очень эффективна по сравнению с AES.

Для 32-битной реализации:

uint32_t next_rand(uint32_t prev) 
{ 
    prev ^= prev << 13; 
    prev ^= prev >> 17; 
    prev ^= prev << 5; 
    return prev; 
} 

Для реализации 64-битной:

последовательности

uint64_t next_rand(uint64_t prev) 
{ 
    prev ^= prev << 21; 
    prev ^= prev >> 35; 
    prev ^= prev << 4; 
    return prev; 
} 

случайного числа "replayable", без гражданства, а зависит только от начального значения, которое это семя.

Ссылки:

1. Wiki: Wiki.

2. Бумага с подробной математикой: paper.