Pseudorandom increasing sequence I am looking for a way to generate an increasing sequence of integers $(x_i)$ such that the sequence of differences $(x_{i+1}-x_i)$ is pseudorandom (in any common way of defining pseudorandomness). It should be possible to efficiently find the $k$-th element in the sequence for a given $k$.

Nonexamples:


A linear congruential generator is not increasing, but it is possible to generate the $k$-th element, $x_k = A^kX_0+(1+\dotsc+A^{k-1})B \pmod{p}$, using $O(log(k))$ arithmetic operations.
Accumulating the sum of a linear congruential generator gives a sequence with the desired pseudorandomness property, but I don't know how to get the $k$-th element efficiently.
Given that you said it would be enough for the sequence to be unpredictable, here is a very simple solution.  The $i$th value in the sequence is given by

$$x_i = 2^{128} i + y_i$$

where $y_i$ is any pseudorandom sequence where you can efficiently find the $i$th value ($y_i$) and where each $y_i$ is 128 bits wide (i.e., $0 \le y_i &lt; 2^{128}$).  For instance, you could use

$$y_i = F(K,i)$$

where $F$ is any pseudorandom function (e.g., AES) with a 128-bit output, and $K$ is a key (the seed from which the entire sequence is generated).