Random access random permutations [closed]

Question

I want to generate a very large pseudorandom permutation p : [0,n-1] -> [0,n-1], and then compute m specific values p[i], where m << n. Is it possible to do this in O(m) time? The motivation is a large parallel computation where each processor only needs to see a small piece of the permutation, but the permutation must be consistent between processors.

Note that in order to help in the parallel case, different processes computing disjoint sets of i values shouldn't accidentally produce p[i] == p[j] for i != j.

Answer 1

An example very low strength version:

1. Generate 2k = O(1) random integers a_i,b_i in [0,n-1], with a_i relatively prime to n.
2. Pick a weak permutation wp : [0,n-1] -> [0,n-1], say w(i) = i with all the but the high bit flipped.
3. p[i] = b_0 + a_0 * wp(b_1 + a_1 * wp(... i ...))

Answer 2

EDIT: There is a much more clever algorithm based on block ciphers that I think Geoff will write up.

There are two common algorithms for generating permutations. Knuth's shuffle is inherently sequential so not a nice choice for parallelism. The other is random selection with retry any time repetition is encountered. Random selection is clearly equivalent when applied in any order, thus I propose the following simple algorithm:

1. Randomly sample candidate p[i] in [0,n-1] for each i in Needed (in parallel).
2. Remove all non-collided entries from Needed, as well as (optionally) some deterministic choice from the collisions (e.g., keep p[i] if i < {j | p[j] = p[i]}).
3. Repeat from step 1 with new (smaller) set Needed.

Since we haven't lost entropy in this process, the result is essentially equivalent to sequential random sampling in some different order, starting with the locations i that did not collide (we just didn't know that order in advance). Note that if we used the computed value in a comparison, for example, we would have introduced bias.