Псевдослучайно выглядящая взаимно-однозначная функция int32->int32

Question

Я ищу функцию int32->int32, которая

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

Answer 1

Умножьте на большое нечетное число, а xor на другое.

Биекция: нечетные числа имеют мультипликативные обратные по модулю степени два, поэтому умножение отменяется умножением на обратное. И xor, конечно, отменен другим xor.

Именно так работает генератор псевдослучайных чисел с линейной конгруэнцией.

Answer 2

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

younumber xor (des (key, number counter))