7
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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/… $\endgroup$ Dec 30, 2012 at 5:39
  • 1
    $\begingroup$ Totally cool. I think it's an interesting question. $\endgroup$ Dec 30, 2012 at 7:49
  • 1
    $\begingroup$ One fun bit is that the inverse of the permutation gives which process owns a given index. $\endgroup$ Dec 30, 2012 at 8:36

1 Answer 1

7
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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$! $\endgroup$
    – Silverfish
    Sep 19, 2023 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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