Задачка выглядит следующим образом.
Например, есть массив на N элементов. Массив последовательно заполняется числами от 0 до N-1, а зетем тщательно перемешивается. Таким образом, по некоторому индексу (seed) в диапазоне от 0 до N-1 можно получить из массива псевдослучайное число (random), а найдя это число (random) в массиве можно узнать его индекс (seed).
Очень не хотелось бы делать такую табличку, т.к. число элементов N=2^32, да и искать потом не очень здорово, хочется обратное преобразование за время = const. Можно ли подобрать такую псевдослучайную функцию и обратную ей, которая обеспечивала бы подобное преобразование?

Можно ли подобрать такую псевдослучайную функцию и обратную ей, которая обеспечивала бы подобное преобразование?
Можно,апроксимируй функцию по всем известным точкам
Но вначале подумай а надо ли это тебе?

Здравствуйте, Pyromancer, Вы писали:

P>Можно,апроксимируй функцию по всем известным точкам ;-)
P>Но вначале подумай а надо ли это тебе?

Если не нужно, я бы не спрашивал.
Меня интересует — существует ли относительно простое (в вычислительном плане) решение этой задачи.
В исходных условиях я забыл уточнить, что все числа целые и положительные, а ответ нужен точный.

Здравствуйте, Аноним, Вы писали:

А>Задачка выглядит следующим образом.
А>Например, есть массив на N элементов. Массив последовательно заполняется числами от 0 до N-1, а зетем тщательно перемешивается. Таким образом, по некоторому индексу (seed) в диапазоне от 0 до N-1 можно получить из массива псевдослучайное число (random), а найдя это число (random) в массиве можно узнать его индекс (seed).
А>Очень не хотелось бы делать такую табличку, т.к. число элементов N=2^32, да и искать потом не очень здорово, хочется обратное преобразование за время = const. Можно ли подобрать такую псевдослучайную функцию и обратную ей, которая обеспечивала бы подобное преобразование?

Любой алгоритм шифрования-дешифрования 32-битного блока. Не важно, симметричный или нет.

Можно по мотивам DES.

Пусть мы имеем следующий набор биективных функций на 32-битных числах:
* сложение с ключом в кольце по модулю 2^32
* умножение на нечетное число в кольце по модулю 2^32 (?)
* побитовое сложение с ключом
* кольцевой сдвиг, а также набор других перестановок битов (в ассортименте). Выбор перестановки из ассортимента — по ключу.
* Биективное преобразование подблоков (например байтов). Выбор функции — по ключу. (Например, имеем некоторое количество таблиц-словарей).

Составляем последовательность таких действий.
Отыграли в одну сторону — зашифровали. Отыграли в другую — расшифровали.

Вероятно, неплохое размешивание даст такая функция:
* составляем таблицу (seed -> rand, rand -> seed) для байтов путем перемешивания чисел 0..255.
* шаг 1: побайтно преобразуем входное 32-битное число.
* шаг 2: сдвигаем число на нецелое количество байт. Например, на полбайта.
* шаг 3: еще раз побайтно преобразуем.