Random number generation with next and previous support?

Question

How to write two functions for generating random numbers that supporting next and previous?

I mean how to write two functions: next_number() and previous_number(), that next_number() function generates a new random number and previous_number() function generates previously generated random number.

for example:

int next_number()
{
   // ...?
}

int previous_number()
{
   // ...?
}

int num;

// Forward random number generating.
// ---> 54, 86, 32, 46, 17
num = next_number(); // num = 54
num = next_number(); // num = 86
num = next_number(); // num = 32
num = next_number(); // num = 46
num = next_number(); // num = 17

// Backward random number generating.
// <--- 17, 46, 32, 86, 54
num = previous_number(); // num = 46
num = previous_number(); // num = 32
num = previous_number(); // num = 86
num = previous_number(); // num = 54

Answer 1

You can trivially do this with a Pseudo-Random Function (PRF).

Such functions take a key and a value, and output a pseudo-random number based on them. You'd select a key from /dev/random that remains the same for the run of the program, and then feed the function an integer that you increment to go forward or decrement to go back.

Here's an example in pseudo-code:

initialize():
    Key = sufficiently many bytes from /dev/random
    N = 0

next_number():
    N = N + 1
    return my_prf(Key, N)

previous_number():
    N = N - 1
    return my_prf(Key, N)

Strong, Pseudo-Random Functions are found in most cryptography libraries. As rici points out, you can also use any encryption function (encryption functions are pseudo-random permutations, a subset of PRFs, and the period is so huge that the difference doesn't matter).

Answer 2

Some linear congruential generators (a common but not very good PRNG) are reversible.

They work by next = (a * previous + c) mod m. That's reversible if a has a modular multiplicative inverse mod m. That's often the case, because m is often a power of two and a is usually odd.

For example for the "MSVC" parameters from the table from the first link:

• m = 2³²
• a = 214013
• c = 2531011

The reverse is:

previous = (current - 2531011) * 0xb9b33155;

With types chosen to make it work modulo 2³².

Answer 3

Suppose you have a linear congruential sequence S defined by

S[0] = seed
S[i] = (p * S[i-1] + k) % m

for some p, m, k such that gcd(p, m) == 1. Then you can find q such that (p * q) % m == 1 and compute:

S[i-1] = (q * (S[i] - k)) % m

In other words: if you pick suitable p and precompute q, you can traverse your sequence in either order in O(1) time.

Answer 4

A reasonably simple way of generating an indexable pseudo-random sequence -- that is, a sequence which looks random, but can be traversed in either direction -- is to choose some (reasonably good) encryption algorithm and a fixed encryption key, and then define:

sequence(i): encrypt(i, known_key)

You don't need to know the value of i, because you can decrypt it from the number:

next(r): encrypt(decrypt(r, known_key) + 1)

prev(r): encrypt(decrypt(r, known_key) - 1)

Consequently, i does not have to be a small integer; since the only arithmetic you need to do to it is addition and subtraction by a small integer, a bignum implementation is trivial. So if you wanted 128-bit pseudorando numbers, you could set the first i to be a 128-bit random number extracted from /dev/random.

You have to keep the entire value of i in static storage, and the period of the pseudorandom numbers cannot be greater than the range of i. That will be true of any solution to this problem, though: since the next() and prev() operators are required to be functions, every value has a unique successor and predecessor, and thus can only appear once in the cycle of values. That's quite different from the Mersenne twister, for example, whose cycle is much larger than 2³².

Answer 5

I think what you are asking for is random number generator that is deterministic. This does not make sense because if it is deterministic, it's not random. The only solution is to generate a list of random numbers and then step back and forward in this list.

PS! I know that essentialy all software PRNG-s are deterministic. You can of course use this to create the functionality you need, but don't fool yourself, it has nothing to do with randomness. If your software design requires having deterministic PRNG then you could probably skip the PRNG part at all.