Reversible pseudo-random sequence generator

Question

I would like some sort of method to create a fairly long sequence of random numbers that I can flip through backwards and forwards. Like a machine with "next" and "previous" buttons, that will give you random numbers.

Something like 10-bit resolution (i.e. positive integers in a range from 0 to 1023) is enough, and a sequence of >100k numbers. It's for a simple game-type app, I don't need encryption-strength randomness or anything, but I want it to feel fairly random. I have a limited amount of memory available though, so I can't just generate a chunk of random data and go through it. I need to get the numbers in "interactive time" - I can easily spend a few ms thinking about the next number, but not comfortably much more than that. Eventually it will run on some sort of microcontroller, probably just an Arduino.

I could do it with a simple linear congruential generator (LCG). Going forwards is simple, to go backwards I'd have to cache the most recent numbers and store some points at intervals so I can recreate the sequence from there.

But maybe there IS some pseudo-random generator that allows you to go both forwards and forwards? It should be possible to hook up two linear feedback shift registers (LFSRs) to roll in different directions, no?

Or maybe I can just get by with garbling the index number using a hash function of some sort? I'm going to try that first.

Any other ideas?

Answer 1

Using a really simple symmetric encryption algorithm is one of the easiest ways to do this. Each random number is formed by just encrypt the previous one with some fixed key and to go backwards you just decrypt.

You might look at the RC4 - Code at http://en.wikipedia.org/wiki/RC4. You could use a much smaller key schedule to get it to all fit on an arduino.

Answer 2

Encrypt the sequence 1, 2, 3, ... with any cipher and any key.

AES is available on just about every recent system out there, and is lightning fast.

Answer 3

Although I agree with @BlueRaja that you should just use AES in "Counter mode", with a random or time-based start for your sequence, AES might not be available or feasible in your embedded situation.

I did find this interesting paper that discusses how to build a reversible PRNG; it's only 10 pages and has plenty of code samples. Give that at try if AES doesn't work for ya.

Answer 4

You can also go backwards with an LCG, it is just another LCG using the inverse of the multiplier modulo the modulus, together with a suitable increment.

For your small numbers you can just use brute force to search for the inverse, in general it can be computed with an extended GCD algorithm.

Unless your game is strictly for fun, with no stakes of whatever kind involved, I would choose something cryptographically secure, such as the AES approach suggested by others. LCGs and other linear random number generators cannot withstand an intelligent adversary.