Discussion:
Indexable PRNG
Joss Knight
2004-08-21 17:23:41 UTC
Raw Message
I am looking for a pseudo-random number generator which allows
efficient random access. I'm not interested in good statistical
properties or an enormously long cycle length, as long as the sequence
appears random (to the eye).

On this group I found an old article concerning the ZIP algorithm,
which is supposedly indexable:

x_i = (2 ^ (i * (p - |p| - 1))) mod p, where |p| is the number of
binary bits of p

at

Problem is, p is both a magic number and defines the cycle length, and
my length needs to be at least several thousand, so (i * (p - |p| -
1)) is very large. I'm not savvy enough to know how to implement this
efficiently. Memory efficiency is also important here, so I can't
afford to hold 2^100000000, or whatever, in memory, even if I knew how
to implement the mod operator for a large block of memory representing
a single integer (in C, for instance), which I don't. This just isn't
my field!

On the link there are implementations of the recursive version of this
algorithm, but if anyone knows how to implement the indexed version,
or knows of other efficient random-access PRNGs, I'd really like to
know about it. I cannot do this by pregenerating a long sequence, for
my application.

Cheers,
Dr Joss Knight

[Probably sci.crypt.research is not exactly the right place for
this kind of question, if you don't need any kind of cryptographic
properties. But, take a look at linear congruential or LFSR generators;
they both permit fast random access to any index in the stream. --DW]
Nick Maclaren
2004-08-21 20:13:29 UTC
Raw Message
Post by Joss Knight
I am looking for a pseudo-random number generator which allows
efficient random access. I'm not interested in good statistical
properties or an enormously long cycle length, as long as the sequence
appears random (to the eye).
Both mutiplicative congruential and shift register are indexable.
In both cases, the formula is:

X_n = X_0 * A^K 'modulo' M

where X_n is the nth value, A is the multiplier and M the modulus.
I put the "modulo M" in quotes, because it really means performing
the multiplication in a particular group. In fact, even the extended
form:

X_n = X_0 * A^K + B 'modulo' M

is indexable, but needs a ring and not just a group. You will find
all of this written up if you can find the right discussion of such
things. But that, as you have found, may not be trivial.

Regards,
Nick Maclaren.
Peter Fairbrother
2004-08-26 15:49:58 UTC
Raw Message
Post by Joss Knight
I am looking for a pseudo-random number generator which allows
efficient random access. I'm not interested in good statistical
properties or an enormously long cycle length, as long as the sequence
appears random (to the eye).
If you have enough cycles and memory, a cheap'n'cheerful way is to run a
cipher in counter mode with a fixed key.

Put simply, you encrypt 1,2,3, .. etc and output the encrypted numbers. You
don't have to start at 1, you can start anywhere you like. The starting
point is the index.

Using AES for instance, you would have the properties you think you don't
need too. And you can have 2^128 different indexable PRNG's, by changing the
fixed key.

--
Peter Fairbrother