Pseudorandom sequence whose values can be computed directly for given seed? Wikipedia says that Blum Blum Shub is a pseudorandom generator whose ith value can be computed directly for a given seed.  Wikipedia also says that this generator is too slow to be practical for simulation applications.
Is there any standard generator with the direct computation property that is fast enough for Monte Carlo?  Is there a reason this cannot exist?
 A: Judging from the comments, is there any reason you can't just put a semaphore around a standard PRNG plus a counter? For example:
  <set a semaphore>
  myPRN = some_PNRG();
  my_number = a_counter++;
  <unset the semaphore>

Assuming your Monte-Carlo simulations take any substantial amount of time to run, the time spent waiting on the semaphore should be relatively insignificant.
A: Although it is not a pseudorandom sequence but rather a low discrepancy sequence, I have been using the Halton sequence for precisely the desired property, i.e. you can calculate the $n$th number in the sequence independently of any others. My motivation for this was also multi-threaded random number generation. Aside from this feature, you may also prefer quasi-Monte Carlo for its faster rate of convergence.
Another approach to consider depending upon the number of random numbers you need is unrolling whereby you pre-generate the random numbers in a large static array which is linked at compile time. Then you can easily random access the $n$th number in the sequence and performance is pretty hard to beat!
A: Based on this thread: https://scicomp.stackexchange.com/a/1281/5065
it is possible to advance to the Nth seed value of a Linear Congruential Generator in O(lg N) ops.  So the LCG is close to a random access PRNG.  Unfortunately its random quality is poor, not good enough for most Monte Carlo, but it can be used for some things...
Alternatively, there seems to be a move towards using strong hash functions for parallel generation; these are inherently randomly addressable.  It's not the simplest method to meet my constraint of being able to match a sequentially generated sequence, but it's doable.
