# Invertible function that randomizes order

I am looking for an invertible discrete function $f:\{0,1,2,\dots,n-1\} \to \{0,1,2,\dots,n-1\}$ for some given integer $n$. I want $f(0),f(1),\dots,f(n-1)$ to return all the integers in range $[0..n)$ exactly once, but in a "messy", random-seeming arrangement. I anticipate that $n$ will be not bigger than $2^{30}$.

I thought about finding a generator for the group <Zn,*>, but I'm not sure if it would work for any given $n$ (would it?). Any other ideas?

• If $n$ is a prime then you can try $ax^{-1} + b$, where $0^{-1} = 0$. – Yuval Filmus Mar 9 '16 at 22:07
• nothing garauntees me that n is prime... need a solution for any n, and i also didnt really see hows the suggested solution fit the needs... but thanks for trying :) – Ofek Ron Mar 9 '16 at 22:08
• Approximately how large is $n$? Which algorithms are practical depends on the order of magnitude. – Gilles 'SO- stop being evil' Mar 9 '16 at 22:12
• n can be any integer most likely not bigger then 2^30, if it helps 2^20 would also be nice. – Ofek Ron Mar 9 '16 at 22:14
• Would keyed families work? ​ If needed, one could probably come up with a sort-of-"canonical" PRF and key. ​ ​ ​ ​ – user12859 Mar 9 '16 at 22:49

You are looking for a pseudorandom permutation on the set $\{0,1,2,\dots,n-1\}$. In cryptography, this has been studied under the (counter-intuitive) name "format-preserving encryption". There are a number of constructions you could use for your purposes.

There's a bunch of research literature on the problem, with different schemes that are optimized for different values of $n$. You can also find some summaries on Cryptography.SE.

I recommend you start by reading the question and the answers at Lazily computing a random permutation of the positive integers and Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher and What are the examples of the easily computable "wild" permutations?.

Well, What i do isnt for encryption and i was looking for something quick and simple, what i did was finding the highest prime p that is smaller than n and a generator g in the group <Z_p,*> , and used the following f :

f(i) = (g^i)modp - 1 if i<n, i otherwise.


I know that the last n-p images are in order but oh well...

• That doesn't solve the problem that you listed in the question, because the resulting map is not a bijection from $\{0,\dots,n-1\}$ to $\{0,\dots,n-1\}$. For instance, suppose $n=3$, so $p=2$, and $g=1$; then your function is $f(0) = 0$, $f(1) = 0$, $f(2) = 0$. That's not a bijection. Or, suppose $n=4$, so $p=3$, and $g=2$; then your function is $f(0) = 0$, $f(1) = 1$, $f(2) = 0$, $f(3) = 1$; again, not a bijection. If you meant i<p instead of i<n, it's still not a bijection; consider the same parameters. – D.W. Mar 11 '16 at 4:13
• the group is <Z_p,*> not <Z_p,+>, so g you mentioned is not a generator edited my answer – Ofek Ron Mar 11 '16 at 9:34
• I think you haven't understood my comment, or you are confused about the definition of generator. $g=2$ certainly is a generator for the multiplicative group of integers modulo $p=3$, i.e., for the group $\mathbb{Z}_3^*$. (And $g=1$ is a generator for the multiplicative group of integers modulo $p=2$.) – D.W. Mar 11 '16 at 10:03
• g=1 is not a generator for p=2, you cant create 0 using 1^i, anyhow, the solution i wrote works for me, so thanks. – Ofek Ron Mar 11 '16 at 13:24
• 0 is not an element of the multiplicative group, as it is not invertible: $\mathbb{Z}_p^*= (\{1,2,3,\dots,p-1\},\times)$. – D.W. Mar 11 '16 at 15:46