Using a sequentially increasing counter to generate an id token is easy. Database sequences and auto-number columns make it fairly trivial to implement. If that isn’t available a simple file or shared memory counter can be implemented in minutes. Displaying such a number to a client however may give them more information than you would really like them to have about the number of ids you are allocating per unit time. We’d really like to obfuscate the id somehow while retaining the uniqueness of the original sequence.
One way to do this is to use a combination of multiplication and modulo arithmetic to map the sequence number into a constrained set. With careful choice of the multiplicative constant and the modulo value the resulting number can be made to wander rather effectively over the entire space of the target set.
The basic math looks like this:
f(n) := (n * p) % q
n:= input sequence value
p:= step size
q:= maximum result size
q must be chosen such that:
q< arithmetic limit (231, 232, 263, 264, … depending on the precision of the underlying system)
q(coprime or relatively prime)
p := 5 and
q := 12 our function will generate this output:
p to 7 and you’ll get:
The rational for keeping
p * q < limit is that as
initial multiplication will approach
p * q and if this calculation overflows
the available precision the result will wrap back into a previously traversed
space causing duplication. The same sort of thing will occur if
are not coprime. The result of the modulo will exhibit a period equivalent to
the GCD1 of
q rather than mapping the entire range of
Careful choice of
q are key to getting a good spread in the output
of the function and maintaining the uniqueness of the result. One easy way to
ensure that the chosen coefficients are coprime is to make them both be prime
powers of prime numbers (eg 917, 1311, 1315, 197, …).
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4
Thanks to Tim for explaining all of this to me several times without becoming annoyed at the parts I wasn’t getting.
Greatest Common Divisor ↩