It is obvious that using seed value one can easily compute next value of some (deterministic) pseudo-random algorithm - so $N$th element can be computed in $O(N)$.


But is there such PRNG that allow to compute Nth element in $O(1)$ while still preserving good periodicity and distribution?



pseudo-random algorithm allowing O(1) computation of Nth element
I think [linear feedback shift registers](http://en.wikipedia.org/wiki/Linear_feedback_shift_register) are examples of what you want. Essentially, these compute powers of $x$ in $F\_2[x]/p(x)$ for some polynomial $p(x)$. If $p(x)$ is chosen well, the period can be long. You can compute $x^n$ rapidly by multiplying $c \log n$ terms of the form $x^{2^k}$ which you can compute by repeated squaring. 


Of course you will probably want to apply some function to the output to reduce the number of bits and to allow the $n$th value to be $0$ and to equal the $n-1$st value. 


