pseudo-random algorithm allowing O(1) computation of Nth element 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?
 A: 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. 
A: The Numerical Recipes book supplies a specific example of a hash-style generator that is up to scratch as a PRNG.  There is a pointer here: http://www.nr.com/forum/showthread.php?t=1653.  The principle is simple: you only need a PRNG that is so thorough that the values generated by seed,seed+1,seed+2,.. are acceptably random.  You can view the code (for free) in section 7.1.4 of the online version of the 3rd edition (via http://www.nr.com), and more importantly the discussion about what qualifies as "up to scratch".  The code amounts to the following:
#include <stdio.h>
#include <inttypes.h>
/* I used http://stackoverflow.com/questions/2844/
 * how-do-you-printf-an-unsigned-long-long-int
 * for advice on uint64_t PRIu64 and inttypes.h */

uint64_t
ranhash(uint64_t v) {
  v *= 3935559000370003845LL;
  v += 2691343689449507681LL;
  v ^= v >> 21; v ^= v << 37; v ^= v >> 4;
  v *= 4768777513237032717LL;
  v ^= v << 20; v ^= v >> 41; v ^= v << 5;
  return v;
}

double
ranhashdoub(uint64_t v) {
  return 5.42101086242752217E-20 * ranhash(v);
}

int
main(int argc, char*argv[])
{
  uint64_t seed = 0; /* same results every time */
  long j;
  for(j=0; j<10; j++)
    printf("%"PRIu64"\n",ranhash(seed++));
  return 0;
}

A: FWIW: any reasonably-secure block cipher in CTR mode is a supposedly-perfect PRNG (if it is not - for about 20 years now, such cipher is not considered secure). 

How to calculate nth element of PRNG using this method:
-- in advance, once -- 


*

*choose cipher C (ranging from rather poor XXTEA to rather secure Chacha20 and AES) and generate some random key K for it (it has to be done once, so K can be taken from random.org or something)


-- to calculate nth element --
1) take number n and copy it into input_block for the cipher C (filling the gaps as necessary) 
2) encrypt input_block with cipher C and key K. Output is supposed to be perfectly-random. 

Pros: (a) secure, which translates into (b) the best-quality RNG out there (any kind of correlation is a severe security weakness, and lots of effort is spent on this kind of analysis). 
Cons: performance is lower than for other PRNGs (though on a single core good implementation can easily reach gigabytes/second).
