Cyclic random-number generation using finite fields

I ran across a very nice post the other day, by Jeff Preshing, about generating non-repeating sequences of pseudo-random numbers. All PRNGs have periods (a fact about functions mapping from finite sets to themselves and the Pigeonhole Principle) but there's a difference between state size and output size. E.g. Mersenne twister has a very long period, but with 624-bit state. You can get repeats on the 32-bit outputs -- as Jeff found. It might be nice to get all 2^32 32-bit integers, permuted, without repeats.

Jeff's approach is to use properties of the finite field F_p, for large p near 2^32 -- in particular, 4296967291 is just 5 shy of 2^32 and he worked around that neatly. But there are also finite fields of order p^n for all p and n -- in particular, p=2 and n=32.

The neat thing is that all p^n-1 non-zero elements of a finite field always form a cyclic group -- there is one non-zero number g (many, really) such that all others are powers of it. For example, mod p=11, g=2 is a generator: its successive powers are 2, 4, 8, 16=5, 32=10, 64=9, 128=7, 256=3, 512=6, 1024=1. You can convince yourself that other generators mod 11 are 6, 7, and 8.

For n>1 the arithemetic is a little (although not too much) more involved. You just have to find an irreducible polynomial r of degree n with coefficients mod p -- this plays the role of the prime -- as well as a generator g. The details are here (including Berlekamp's algorithm) but for example one can use r = 0x17bc0cb37 -- a 33-bit number so all the residues have 32 bits -- and g = 0xb139e84d. (I got these particular values using RUFFL, generating random 32-degree polynomials until I found one which is irreducible, and likewise found a g with full period 2^32-1.) Note that if you need period 2^32 rather than 2^32-1 you can special-case that: e.g. if the PNRG gives a maps to f(a) then just use an if-statement to splice in a maps to 0 maps to f(a); maybe pick a = 0xdeadbeef, or anything else.

Jeff used TestU01 to run some statistical tests on his cyclic generator. This is a C library so I used iff2 to try it out.

The generator is simply


int      degr  = 32;
unsigned r     = 0x7bc0cb37;
unsigned g     = 0xb139e84d; // 2 ** 65539
unsigned state = 2;

unsigned f232() {
    state = iff2mul(state, g, r, degr);
    return state;
}

and you can seed it by setting state to anything non-zero.

Using this I found:

* (+) The mathematical theory gives you full period very cleanly.
* (+) You can seed by simply setting the state variable.
* (+) State is only 32 bits (96 if you count r and g).
* (-) To generate a different permutation entirely, you need not just any 32-bit number g but rather one which is a generator.  This makes the parameterization a bit less user-friendly.
* (-) I didn't get as good results with TestU01's SmallCrush suite as Jeff got with his permuteQPR -- tests 1 and 8 have p-value of eps.  More experimenting with r's and g's might give better results.