What are the examples of the easily computable “wild” permutations?

Question

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| < 100$ the outputs of the function should differ very much $|f(x_1) - f(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:

1. 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.

2. 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}$.

3. 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 object I am looking for)?

Answer 1

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.