# Random access random permutations

I have a large number of parallel processes and a large integer $$n$$, and want to randomly partition the integers $$[0,n)$$ among the processes with only $$O(1)$$ communication.

One nice way to do this would to generate a pseudorandom permutation $$\pi \in S_n$$ represented as a small function, so that only the random key/seed need be exchanged. Is there a good way to do this?

• I'm about to answer this myself. I was about to answer it on stackoverflow, but it was closed as "not a question": stackoverflow.com/questions/14077953/… Dec 30, 2012 at 5:39
• Totally cool. I think it's an interesting question. Dec 30, 2012 at 7:49
• One fun bit is that the inverse of the permutation gives which process owns a given index. Dec 30, 2012 at 8:36

Pick $2^k$ slightly larger than $n$, generate a block cypher $f \in S_{2^k}$ operating on $k$ bit blocks, and construct a permutation on $[0,n)$ by walking along cycles of $f$ until we get back in the desired range. Specifically, given $x < n$ we set $$g(x) = f^p(x) = f(f(f(...x...)))$$ where $p$ is the least positive integer s.t. $f^p(x) < n$.

If $2^k = O(n)$, and the block cypher is good, the walk takes $O(1)$ expected time. Note that $p$ is necessarily finite, since eventually we will walk back around the cycle and find $f^p(x) = x$.

For more details, see

1. Black and Rogaway, Ciphers with Arbitrary Finite Domains, 2001.
2. http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Secure-permutations-with-block-ciphers

Here is an example implementation using a truncated TEA block cypher as described in (2):

https://github.com/otherlab/core/blob/f09fbd19dbaa7b9033eb0888594273a6a3d592a5/random/permute.cpp

• Trivial, but I found it interesting: this trick isn't limited to finding pseudorandom permututations of sets of the form $\{0,1,\dots,n-1\}$ but all sorts of weird/wonderful sets. Don't even need to precompute/store the set if it has a simple membership test! Eg to find $g$ that permutes the set $S=\{1677,2717,2977,3757,\dots,9776\}$ of "four-digit numbers divisible by 13 in which the digit 7 appears at least twice", it's enough to note $2^{14}>\max(S)$, take $k=14$, then iterate $f$ until the output passes the membership test for $S$! Sep 19, 2023 at 21:02