Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
How do you define efficiently? Presumably you mean less than $O(k)$. –  Dave Clarke Mar 18 '12 at 20:50
    
@DaveClarke: Yes. Less than O(k). And hopefully much closer to O(log(k)). –  user302099 Mar 18 '12 at 22:11
4  
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. –  Tsuyoshi Ito Mar 18 '12 at 22:26
    
Please define "pseudorandom". Do you mean "approximately uniform"? Or do you just mean "unpredictable"? –  JɛffE Mar 19 '12 at 9:19
2  
Did you read my previous comment? –  Tsuyoshi Ito Mar 20 '12 at 0:40
show 1 more comment

1 Answer 1

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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