Существует ли «хороший» PRNG, генерирующий значения без скрытого состояния?

Question

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

1. Я должен иметь возможность параметризовать генератор таким образом, чтобы запуск его для 2^n итераций с любыми параметрами (или с некоторым большим их подмножеством) охватывал все или почти все значения между 0 и 2^n - 1, где n - количество битов в выходном значении.

2. Комбинированный вывод генератора из n + p битов должен охватывать все или почти все значения между 0 и 2^(n + p) - 1, если я запускаю его для 2^n итераций для каждой возможной комбинации его параметров, где p количество бит в параметрах.

Например, LCG может быть вычислено как чистая функция и может соответствовать первому условию, но не может соответствовать второму. Скажем, у нас 32-битный LCG, m = 2^32 и он постоянный, наши p = 64 (два 32-битных параметра a и c), n + p = 96, поэтому мы должны просматривать данные на три дюйма от вывода встретить второе условие. К сожалению, условие не может быть выполнено из-за строго чередующейся последовательности нечетных и четных чисел в выходных данных. Чтобы преодолеть это, необходимо ввести скрытое состояние, но это делает функцию не чистой и нарушает первое условие (длинный скрытый период).

РЕДАКТИРОВАТЬ: Строго говоря, я хочу, чтобы семейство функций параметризовалось p битами и с полным состоянием n битов, каждая из которых генерировала все возможные двоичные строки p + n битов в уникальном "случайном" "Кстати, не просто непрерывно увеличивая (p + n) -bit Int. Параметризация требуется для выбора этого уникального пути.

Хочу ли я слишком многого?

Answer 1

Вы можете использовать любой блочный шифр с фиксированным ключом. Чтобы сгенерировать следующий номер, расшифруйте текущий, увеличьте его и повторно зашифруйте. Поскольку блочные шифры имеют размер 1: 1, они обязательно будут перебирать все числа в выходной области перед повторением.

Answer 2

Попробуйте LFSR
Все, что вам нужно, это список примитивных полиномов.
Период генерации конечного поля таким образом, порождает поле размером 2 ^ n-1. Но вы можете обобщить эту процедуру, чтобы сгенерировать что-нибудь с периодом k ^ n-1.

Я не видел, чтобы это было реализовано, но все, что вам нужно реализовать, это сдвигать числа на малые числа s> n, где gcd (s, 2 ^ n-1) == 1. gcd обозначает наибольший общий делитель