Applied algebra

Today I faced a problem: how to generate a pseudo-random permutation of numbers in range [0,2^128), such that each number appears exactly once. An obvious solution is to initialize an array A[i]=i and then shuffle elements with repeated calls to random(). However, that would use a large amount of memory, which is not acceptable in this particular case.

So I remembered a bit of algebra that I learned long time ago at the university. It's about cyclic groups. Consider the sequence k*a0 % M for k = 0, 1, .... In my case M=2^128. This sequence generates all numbers less than M exactly once, provided that a0 and M are relatively prime. Shortly, a0 is a generator of an additive cyclic group where the set of elements are natural numbers in the range G=[0,2^128), and the operation is addition modulo M.

The code is even simpler (pseudo-C):

a = 0;
do {
  /* use a in some way */
  a += a0;
  if(a > M) a -= M;
} while(a);

When a becomes 0 again, the whole group of M elements has been generated, so the loop exits. In other words, a has cycled through all elements in G exactly once. This is also connected with pseudo-random number generators. I'm not interested in the exact statistical properties of generated numbers; the only requirement is that consecutive numbers are "far enough" apart (which I define by chosing an appropriate constant a0).

Tags: algebra random numbers