views:

167

answers:

2

I need some good pseudo random number generator that can be computed like a pure function from its previous output without any state hiding. Under "good" I mean:

  1. I must be able to parametrize generator in such way that running it for 2^n iterations with any parameters (or with some large subset of them) should cover all or almost all values between 0 and 2^n - 1, where n is the number of bits in output value.

  2. Combined generator output of n + p bits must cover all or almost all values between 0 and 2^(n + p) - 1 if I run it for 2^n iterations for every possible combination of its parameters, where p is the number of bits in parameters.

For example, LCG can be computed like a pure function and it can meet first condition, but it can not meet second one. Say, we have 32-bit LCG, m = 2^32 and it is constant, our p = 64 (two 32-bit parameters a and c), n + p = 96, so we must peek data by three ints from output to meet second condition. Unfortunately, condition can not be meet because of strictly alternating sequence of odd and even ints in output. To overcome this, hidden state must be introduced, but that makes function not pure and breaks first condition (long hidden period).

EDIT: Strictly speaking, I want family of functions parametrized by p bits and with full state of n bits, each generating all possible binary strings of p + n bits in unique "randomish" way, not just continuously incrementing (p + n)-bit int. Parametrization required to select that unique way.

Am I wanting too much?

+1  A: 

Try LFSR
All you need is list of primitive polynomials.
Period of generating finite field this way, generates field of size 2^n-1. But you can generalise this procedure to generate anything whit period of k^n-1.

I have not seen this implemented, but all you have to implement is shifting numbers by small number s>n where gcd(s,2^n-1) == 1. gcd stands for greatest common divisor

ralu
As I understand, there is subset of combined values containing zeros that can not be generated.
actual
That is true. You should manualy add support for zeroes if you need it and just jump from predefined value for instance 0x001 to 0x000 and than back to next value of 0x001.
ralu
+2  A: 

You can use any block cipher, with a fixed key. To generate the next number, decrypt the current one, increment it, and re-encrypt it. Because block ciphers are 1:1, they'll necessarily iterate through every number in the output domain before repeating.

Nick Johnson
Interesting idea, but too slow for my application. Any way, thanks.
actual
Hmm... maybe not so slow. How do you think will it work, if I will generate key of width p, not n + p, and start XORing it with data of n + p width. Will it generate all combinations of n + p width?
actual
Depends where you get the data. Broadly speaking, that probably won't generate a permutation.
Nick Johnson