Ищете PRNG приличного качества только с 32 битами состояния

Одним из хороших (но, вероятно, не самых быстрых) вариантов, предлагающих очень высокое качество, было бы использование 32-битного блока . шифр в режиме CTR. По сути, ваше состояние RNG будет просто 32-битным счетчиком, который увеличивается на единицу при каждом вызове RNG, а результатом будет шифрование этого значения счетчика с использованием блочного шифра с некоторым произвольно выбранным фиксированным ключом. Для дополнительной случайности вы можете даже предоставить (нестандартную) функцию, позволяющую пользователю установить собственный ключ.

Существует не так много широко используемых 32-битных блочных шифров, поскольку такой короткий размер блока создает проблемы для криптографического использования. (По сути, парадокс дня рождения позволяет отличить вывод такого шифра от случайной функции с непренебрежимо малая вероятность после примерно 2¹⁶ = 65536 выходов, а после 2³² выходов неслучайность, очевидно, становится очевидной.) Однако некоторые шифры с регулируемым размером блока , например XXTEA или HPC позволит вам перейти на 32-битную версию и подойдет для ваших целей.

(Редактировать: Плохо, XXTEA использует только 64-разрядную версию. Однако, как предлагает CodesInChaos в комментариях, Skip32 может быть другим вариантом. Или вы можете создать свой собственный 32-разрядный шифр Фейстеля.)

Конструкция режима CTR гарантирует, что RNG будет иметь полный период из 2³² выходов, в то время как стандартное требование безопасности (не взломанных) блочных шифров по существу состоит в том, что вычислительно невозможно различить их выходные данные. из случайной перестановки набора 32-битных целых чисел. (Конечно, как отмечалось выше, такую ​​перестановку легко отличить от случайной функции принимает 32-битные значения.)

Использование режима CTR также предоставляет некоторые дополнительные функции, которые могут оказаться удобными (даже если они не являются частью официального API, для которого вы разрабатываете), такие как возможность быстрого поиска в любой точке выходного потока RNG, просто добавляя или вычитание из состояния.

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

Уточняю мой комментарий...

Блочный шифр в режиме счетчика дает генератор примерно в следующем виде (за исключением использования гораздо больших типов данных):

uint32_t state = 0;
uint32_t rand()
{
    state = next(state);
    return temper(state);
}

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

Один подход состоит в том, что функция next() проста (например, return state + 1;), а temper() компенсируется сложностью (как в блочном шифре).

Более сбалансированный подход состоит в том, чтобы реализовать LCG в next(), поскольку мы знаем, что он также посещает все возможные состояния, но в случайном порядке, и найти реализацию temper(), которая выполняет ровно столько работы, сколько необходимо для решения оставшихся проблем с LCG.

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

У меня есть любимый способ: перевернуть слово, а затем умножить его на некоторое постоянное (нечетное) число. Это может быть слишком сложным, если бит-реверс не является родной операцией в вашей архитектуре.

Вам может подойти 32-битный LFSR Галуа с максимальным периодом. Пытаться:

r = (r >> 1) ^ (-(r & 1) & 0x80200003);

Единственная проблема с LFSR заключается в том, что вы не можете получить значение 0. Таким образом, этот имеет диапазон от 1 до 2 ^ 32-1. Вы можете настроить вывод или использовать хороший LCG.

Помимо использования Lehmer MCG, вы можете использовать еще пару:

32-разрядные варианты Xorshift имеют гарантированный период 2 ³²−1 с использованием 32-битного состояния:

uint32_t state;

uint32_t xorshift32(void) {
    state ^= state << 13;
    state ^= state >> 17;
    state ^= state << 5;
    return state;
}

Это исходная 32-битная рекомендация от 2003 года (см. статью). В зависимости от вашего определения «приличного качества», это должно быть хорошо. Однако он не прошел бинарные ранговые тесты Diehard и 5/10 тестов SmallCrush.

Альтернативная версия с улучшенным микшированием и константами (уступает SmallCrush и Crush):

uint32_t xorshift32amx(void) {
    int s = __builtin_bswap32(state * 1597334677);
    state ^= state << 13;
    state ^= state >> 17;
    state ^= state << 5;
    return state + s;
}

На основе исследований здесь и здесь.

Есть также Mulberry32 с периодом ровно 2 ³²:

uint32_t mulberry32(void) {
    uint32_t z = state += 0x6D2B79F5;
    z = (z ^ z >> 15) * (1 | z);
    z ^= z + (z ^ z >> 7) * (61 | z);
    return z ^ z >> 14;
}

Это, вероятно, ваш лучший вариант. Это очень хорошо. Автор заявляет: «Он проходит 13 тестов Gjrand без сбоев и общего значения P 0,984 (где 1 идеально, а 0,1 или меньше - сбой) на 4 ГБ сгенерированных данных. Это четверть полного периода». Похоже, это улучшение по сравнению с SplitMix32.

"SplitMix32", заимствованный из xxHash/MurmurHash3 (последовательность Вейля):

uint32_t splitmix32(void) {
    uint32_t z = state += 0x9e3779b9;
    z ^= z >> 15; // 16 for murmur3
    z *= 0x85ebca6b;
    z ^= z >> 13;
    z *= 0xc2b2ae35;
    return z ^= z >> 16;
}

Качество здесь может быть сомнительным, но у его 64-битного старшего брата множество поклонников (проходит BigCrush). Так что стоит посмотреть на общую структуру.