What are the examples of the easily computable "wild" permutations?

I am looking for the function $y=f(x)$ that would map the integer interval $[0,n)$ into itself $[0,n)$. The function must be bijective, so it is a permutation of n elements. It should "randomize" the input variable, ie.

• for every $x_1$ and $x_2$ that are close $|x_1 - x_2| n/{100}$

• changing any digit in the input should change most of digits in the output

• Shannon's Confusion and diffusion: http://en.wikipedia.org/wiki/Confusion_and_diffusion

• There should be very little or no fixed points (for every $x$: $f(x) \neq x$).

or any combination of the above conditions.

I don't need the inverse function. It should also be easy to compute from the closed form expression (a maximum of a few thousands simple computer operations like addition, multiplication, modulo etc.) for $n=10^{100}$.

I found some examples in Google:

• Linear congruential generator. Equation:

$X_{n+1} = (aX_n + c) \mod m$

Wikipedia states that: "Provided that the offset $c$ is nonzero, the LCG will have a full period for all seed values if and only if:

• $c$ and $m$ are relatively prime,

• $a - 1$ is divisible by all prime factors of $m$,

• $a - 1$ is a multiple of 4 if $m$ is a multiple of 4.

I've tried using another function $f(x) = (ax + c) \mod m$, because I wanted to get rid of the recursion, and as long as $m$ is prime and $a \ge 1$ I get the permutation. However the result is not that "wild" or "chaotic" as I expect it to be.

• Minimal perfect hash function

The concept is similar to what I'm looking for, but if I understand correctly the computation of this kind of function is very complicated and time-consuming and it cannot be expressed in a closed form as a simple expression for $n=10^{100}$.

• Substitution-permutation network

I am not sure how to apply S-boxes and P-boxes to the interval [0,n), but maybe it could be used.

The question is: Could you give me some examples of functions that satisfy the above conditions (or some pointers like the mathematical term for the

Yes, such things exist. They have been studied in the cryptographic literature: the key name is "format-preserving encryption".

To learn about this subject, I suggest taking a look at https://en.wikipedia.org/wiki/Format-preserving_encryption and https://crypto.stackexchange.com/q/16561/351 and https://crypto.stackexchange.com/q/504/351 and https://crypto.stackexchange.com/q/20035/351 and https://crypto.stackexchange.com/q/18988/351 and
https://crypto.stackexchange.com/questions/tagged/format-preserving. You could also construct a suitable block cipher yourself using a Feistel construction, but it's probably better to use a standard scheme that has been analyzed in the literature.

There are many constructions. The best one will depend on the specific value of $n$ in your application. Take a look at the schemes in the cryptographic literature, then if you have a more specific question about how to use one of those schemes, you can ask either here or on Crypto.SE.

StackExchange Computer Science Q#41124, answer score: 3