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:

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

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

• How do you define efficiently? Presumably you mean less than $O(k)$. Mar 18 '12 at 20:50
• @DaveClarke: Yes. Less than O(k). And hopefully much closer to O(log(k)). Mar 18 '12 at 22:11
• Are you sure that the sequence $\{x_k\}$ defined by recurrence $x_{k+1}=Ax_k+B \bmod p$ is pseudorandom enough for you? It is not pseudorandom in almost any definition because given p (which is usually fixed), the whole sequence can be predicted from the first three terms. Mar 18 '12 at 22:26
• Please define "pseudorandom". Do you mean "approximately uniform"? Or do you just mean "unpredictable"? Mar 19 '12 at 9:19
• Did you read my previous comment? Mar 20 '12 at 0:40

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