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


  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.

  • $\begingroup$ How do you define efficiently? Presumably you mean less than $O(k)$. $\endgroup$ Mar 18 '12 at 20:50
  • $\begingroup$ @DaveClarke: Yes. Less than O(k). And hopefully much closer to O(log(k)). $\endgroup$
    – user302099
    Mar 18 '12 at 22:11
  • 4
    $\begingroup$ 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. $\endgroup$ Mar 18 '12 at 22:26
  • $\begingroup$ Please define "pseudorandom". Do you mean "approximately uniform"? Or do you just mean "unpredictable"? $\endgroup$
    – Jeffε
    Mar 19 '12 at 9:19
  • 2
    $\begingroup$ Did you read my previous comment? $\endgroup$ 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.