Эффективный расчет n-го элемента в случайной перестановке

Question

Представьте, что я смог перетасовать все числа от 0 до 2 ^ 32, используя что-то вроде перемешивания Кнута и генератора случайных чисел, засеянного ключом.

Концептуально, мне понадобятся два массива (используя Z ₅ вместо Z _{2 ³²} для краткости):

[2, 0, 1, 4, 3] // perm
[1, 2, 0, 4, 3] // inv === p^-1

ЕслиУ меня были эти массивы, я мог бы эффективно найти n-й элемент в перестановке, а также узнать с помощью элемента в значении пурмутации v;

v = perm[n];
n == inv[v]; // true

Я не хочу хранить два массива по 16 ГБuint, представляющий это перемешанное множество, потому что я никогда не интересуюсь всей перемешанной последовательностью.Меня интересует только значение n-го элемента.

В идеале я хочу написать две чистые функции, которые работают так:

uint nthShuffled = permutate<uint>(key, n); // O(log n)
uint n == invert<uint>(key, nthShuffled); // O(log n)

Требования:

• Каждое 32-битное значение соответствует уникальному другому 32-битному значению.
• Знание первых 100 элементов в перестановке не дает информации о том, что может быть 101-м элементом в перестановке.

Я понимаю, что в теории должно быть не менее 2 ³² !уникальные ключи для представления любой возможной перестановки, но я полагаю, что на практике я могу скрыть эту проблему за хорошей функцией хеширования.

Есть ли что-нибудь, что близко к этому?

Answer 1

Любой блочный шифр на самом деле является псевдослучайной перестановкой. 32-битный блочный шифр переставляет целые числа между 0 и 2 ^ 32 - 1.

Учитывая секретный ключ, шифрование N с этим ключом дает N-th псевдослучайное число.

Единственная проблема - найти хороший 32-битный блочный шифр. Единственный, кого я знаю, это SKIP32 , но я ничего не знаю о его силе.

Размер ключа SKIP32 составляет 80 бит. Если это хороший шифр, этого будет достаточно.

Но опять же, я не знаю шифр.

Если увеличение диапазона до 2 ^ 64 - 1 целых чисел - вариант для вас, вы можете просто использовать известный 64-битный блочный шифр, такой как Triple-DES или Blowfish.

Answer 2

"Знание первых 100 элементов в перестановке не дает информации о том, что может быть 101-м элементом в перестановке."

Вам необходимо сохранить весь массив в памяти.Я предлагаю использовать stxxl, который предназначен для больших типов данных, храня большую часть контейнера на диске.По самой природе случайной перестановки вы не можете экстраполировать значение [n-1] или [n + 1] с учетом [n].Так что не похоже, что пространство можно оптимизировать.

Answer 3

С криптографической точки зрения вам нужен блочный шифр с 32-битными блоками.

Проблема шифрования (так называемая «перестановка с ключами») на произвольных (и часто небольших) доменах заключается в том, о чем Форматно-сохраняющее шифрование .

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

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

Стандартного и безопасного 32-разрядного блочного шифра не существует, поскольку 32-разрядного недостаточно для обеспечения безопасности в ситуациях, когда широко используются блочные шифры (шифрование длинных потоков данных, например, как часть SSL). ); 64-битные блоки уже не одобряются. Так что вы здесь немного одиноки.

Answer 4

Хеширование не происходит, поэтому решайте последовательности случайных чисел.

Хранить 2 ^ 32 бита. Это 0,5 ГБ.

Запустите перетасовку Фишера-Йейтса и "вычеркните" биты по мере продвижения вперед. Если вы хотите узнать содержание 5-го элемента, вы вычеркнете 4, а 5-е случайное значение будет вашим числом.

Чтобы получить n-ю перестановку, вам нужно вернуться назад. Запустите алгоритм n раз и получите числа вроде:

Find 5th index after 4 permutations:

First iteration:
1st : skip (run through the RNG)
2nd : skip
3rd : skip
4th : 7th index to 5th index
Second iteration: (run using same seed as 1st iteration)
1st : skip
2nd : skip
3rd : 3rd index to 7th index
4th : 7th index to 5th index
Third iteration:
1st : skip
2nd : 4th index to 7th index
3rd : 3rd index to 7th index
4th : 7th index to 5th index
Fourth iteration:
1st : 8th index to 4th index
2nd : 4th index to 7th index
3rd : 3rd index to 7th index
4th : 7th index to 5th index

К последней итерации вы знаете, что 8-й индекс ведет к 5-му.

РЕДАКТИРОВАТЬ: я написал быструю программу для проверки скорости. Это займет несколько минут на перестановку. Это медленно, но все еще пригодно для использования.