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?
Best Answer
I think linear feedback shift registers 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.