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