Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 $p \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?

share|improve this question
I'm about to answer this myself. I was about to answer it on stackoverflow, but it was closed as "not a question":… – Geoffrey Irving Dec 30 '12 at 5:39
Totally cool. I think it's an interesting question. – Geoff Oxberry Dec 30 '12 at 7:49
One fun bit is that the inverse of the permutation gives which process owns a given index. – Geoffrey Irving Dec 30 '12 at 8:36
up vote 5 down vote accepted

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.

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.