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).

afterexisting should take N computations. $\endgroup$ – John Rivers Aug 17 '12 at 14:57