Псевдослучайная циклическая перестановка

[Tookser]

Можно взять все целые числа от 0 до N-1 и рассмотреть какую-нибудь циклическую перестановку. Например, прибавление 1 по модулю $N$. Но такая перестановка выглядит слишком "простой" и неслучайной, хотя считается очень быстро.

Пусть $N = 256^{K \cdot L} $
где $K$ и $L$ - небольшие (до $4000$) натуральные числа.
Можно ли придумать какую-нибудь циклическую перестановку, тоже вычисляющуюся быстро, но на вид более случайную?
Сразу приходит в голову прибавление какого-то числа, взаимнопростого с $N$, но это выглядит не очень случайно.
Быстро вычисляющуюся - например, на обычном процессоре, хотя можно и GPU.
Теущее число хранится в памяти как беззнаковое целое.

(Оффтоп)

Задача возникла из идеи из какого-то художественного произведения. Там был растровый экран, на котором в пиксельном виде каждую секунду появлялось новое изображение, причём так, что за огромное время все возможные изображения были бы выведены. Понятно, что за секунду можно довольно сложное посчитать, но интересно, что можно посчитать ещё быстрее.

[Dmitriy40]

Хорошо работают циклические коды (в частности разные виды CRC), реализуются как регистр сдвига с обратной связью или в языке программирования С как операция x=(x&1)?(x>>1)^<маска>:x>>1;. При правильном выборе порождающего полинома (маски) имеют период ровно $2^n-1$, n - длина регистра/переменной в битах. Одно выделенное состояние (обычно нулевое) легко проверить отдельно. Визуально - полный хаос, что и требовалось. Я так и делал именно такую задачу.
Если нужен период меньше чем выдаёт генератор, то или взять результат по модулю нужного периода, или использовать младшие биты, или считать значение дробной частью числа и домножить на желаемый период и использовать целую часть, или повторять шаги до получения числа меньшего желаемого периода. Первые три варианты могут выдавать повторяющиеся значения!
Категорически не рекомендую самому "от фонаря" выбирать порождающий полином (маску) - можно получить период значительно меньше максимального и зависящий от начального значения, лучше взять любой из уже используемых (в методах CRC) полиномов или перед использованием проверить период.

[Dmitriy40]

Я не прав, полиномы CRC далеко не всегда дают максимальный период. Например для 8-ми битного генератора максимальный период дают лишь следующие полиномы (привожу маску для вычислений выше): 0x8E, 0x95, 0x96, 0xA6, 0xAF, 0xB1, 0xB2, 0xB4, 0xB8, 0xC3, 0xC6, 0xD4, 0xE1, 0xE7, 0xF3, 0xFA. Для 16-ти битного генератора полиномов уже 2048 штук.
Посмотреть на готовые полиномы можно в вики. А здесь есть и полный список полиномов длины от 4 до 32 (ссылка из вики).

[realeugene]

Tookser в сообщении #1231971 писал(а):

Можно ли придумать какую-нибудь циклическую перестановку,

Циклическую перестановку чего?

Если вам нужно просто сгенерировать псевдослучайную последовательность, которую можно легко циклически сдвигать на какое-то задаваемое снаружи число позиций - то просто пропустите счётчик через хороший блочный шифр. Тогда изменяя начальное состояние счётчика вы получите циклический сдвиг вашей последовательности. А если кому-то удастся обнаружить в этой последовательности какие-либо корреляции, значит, вы выбрали плохой шифр. Обратимость функции шифрования гарантирует отсутствие повторений.

[Tookser]

realeugene в сообщении #1235681 писал(а):

Tookser в сообщении #1231971 писал(а):

Можно ли придумать какую-нибудь циклическую перестановку,

Циклическую перестановку чего?

Если вам нужно просто сгенерировать псевдослучайную последовательность, которую можно легко циклически сдвигать на какое-то задаваемое снаружи число позиций - то просто пропустите счётчик через хороший блочный шифр. Тогда изменяя начальное состояние счётчика вы получите циклический сдвиг вашей последовательности. А если кому-то удастся обнаружить в этой последовательности какие-либо корреляции, значит, вы выбрали плохой шифр. Обратимость функции шифрования гарантирует отсутствие повторений.

Имел в виду циклическую перестановку чисел от 0 до $N$, где $N = 256^{K \cdot L} $.
Т.е. требуется псевдослучайная последовательность без повторов, включающая все числа от 0 до N по 1 разу. Шифр же не обязан по всем числам пройтись при повторном применении?

[realeugene]

Tookser в сообщении #1243085 писал(а):

Шифр же не обязан по всем числам пройтись при повторном применении?

Шифр - это взаимно однозначное отображение блоков соответствующей длины. Если у вас значение вашего $256^{K \cdot L}$-битного счётчика на входе не повторяется, то и результат его шифрования всегда будет разный. Иначе, вы не смогли бы этот результат на выходе расшифровать, получив обратно значение вашего счетчика.

Другое дело, что блочный шифр для такого длинного блока нужно конструировать из более коротких блочных шифров, и это тоже требует аккуратности, чтобы, во-первых, сохранилась обратимость шифра, гарантирующая отсутствие повторов, и во-вторых, чтобы обеспечить перемешивание, чтобы каждый входной бит влиял на каждый выходной. Например, шифровать ваш длинный блок коротким блочным шифром в режиме CBC за два прохода, перевернув между проходами битовый вектор. И c заранее фиксированными начальными векторами (можно нулевыми).

Сколько времени вы будете перебирать все значения вашего $256^{K \cdot L}$-битного счётчика, это отдельный вопрос. Не в этом мире. Но отсутствие повторов гарантируется.

Tookser в сообщении #1243085 писал(а):

Имел в виду циклическую перестановку чисел от 0 до $N$, где $N = 256^{K \cdot L} $.

Переставлять циклически можно только последовательность чисел, но не их множество. Какая ваша исходная последовательность, которую вы хотите переставлять циклически? Все числа от 1 до $N$ в порядке возрастания? Тогда у вас всё гораздо проще. Начинайте считать числа со случайной позиции в порядке возрастания, и считайте по модулю $N$. Или же ваша начальная последовательность, переставляемая циклически, сама есть некоторая фиксированная псевдослучайная перестановка последовательности чисел 1 до $N$ в порядке возрастания? Тогда делайте как я подсказываю.

[realeugene]

Точнее, счётчик вам нужен всего $8 K L\le 128\,000\,000$-битный. Полный перебор у вас займёт примерно $10^{38531839}$ текущих возрастов Вселенной

[maxal]

Tookser, если нужно что-то простенькое, то посмотрите на Lehmer random number generator.
Для ваших целей берете простой модуль $n$ чуть больше $N$ и первообразный корень $g$ по модулю $n$. Тогда $X_0, X_1, \dots$ как раз и даст циклическую перестановку чисел $1,2,\dots,n-1$. Элементы большие $N$ из нее можно просто выкинуть.