The actual maths behind the sequence is not very complicated.

The number Generators

Each number generator uses what is called a Linear Feedback Shift Register(LFSR). There are all sorts of details about these magical mechanisms online but essentially, if you feed it a starting value of 1 and a degree-n Primitive Polynomial as a tap function it will produce a sequence of numbers that visits every possible number between 1 and 2^n-1 in what seems like a random sequence. Actually, the sequence is so nicely random it even passes all sorts of statistical tests for randomness.

An LFSR can be designed to generate a sequence covering any number of bits - you just need the computing power to pick a primitive polynomial that spans that many bits. They actualy aren't that difficult to find, there are lists online and the maths is comparatively simple to derive your own. It takes a while but not years like some of the cryptography algorithms, more like a few hours on a laptop or a few minutes on a multi-core desktop.

95 Bits

I decided to pick a Primitive Polynomial that will deliver 95-bit numbers.

I choose 95 bits for two reasons, firstly 95 is one bit less than a multiple of 8. You can therefore, if you wish, store it as a binary number in 12 bytes with no fear of ever coming across a negative number. You'd be surprised how easy that makes things.

The second reason is that 95 is a multiple of 5 so you can also store it as a 19-digit base-32 number. This has connections with the credit card industry. All current credit card numbers have an upper length limit of 19 digits. If the international standards for representing card numbers were relaxed enough to include base-32 characters instead of just digits my numbers would fit in seamlessly as credit card numbers.

255 bit numbers have similar characteristics but with drastically longer lifetimes. 15 bit works too but the sequences would be a bit short.

Slicing them up

We now have a sequence of all 95-bit numbers being faithfully generated by our LFSR. How am I going to make sure that no-one ever gets the same number? There are 39,614,081,257,132,168,796,771,975,168 numbers in the sequence (so I am informed here). This is going to last a long time.

Here's the first clever bit - I'm going to mark every k-bit number in that sequence as a break-point. All sequences will start at a k-bit number and continue until it reaches the next k-bit number. At which point it will cease to function. I can now choose k so that I balance how many sequences there are with how many numbers there are in each sequence. For example, if k was 2 I would have 3, 5, 6, 9,10, ... as starting points.

The way an LFSR functions causes even numbers to be divided by two and odd numbers to be tapped so actually, all of those even start points will cascade to an odd number before embarking on their long journey. The number of k-bit numbers in an n-bit number can be calculated using Pascals Triangle. The number can be read off from the nth row at position k-1 (not k because of the even numbers thing).

Picking K

K can be chosen with a little back-of-the-envelope maths and some finger-in-the-air estimates. I want sequences that are a reasonable number of years long (at one number per millisecond) while ensuring that there were enough generators that I could sell for a fraction of a penny/cent each and still make some pocket money.

I picked 15 bits for a number of quite arbitrary reasons - not least of which being that 15 is the next lower special number that satisfies my initial parameters (2^n - 1 and multiple of 5), so it has a kind of poetic synergy. Also, the sequence lengths are impressive (60+ years long at one per millisecond) and the possible generators couldn't possibly run out (20,439,879,147,794,490).

Picking the primitive

Surprisingly, this is a much more complicated question than you would expect. I have to accept that it is unlikely that the primitive I pick will remain a secret. If an odd number is obtained from a specific generator and the following number is also captured from the same generator then it is possible to directly calculate the primitive.

I can code to make this difficult. I can run a number of generators in parallel and pick from each at random. Behind this website there is actually a 10-generator pack supplying the numbers. Which generator to use for each number generated is chosen at random.

I believe so long as we accept that the primitive will be discovered eventually (or even quickly) we can code to avoid that being a problem. Making it difficult to obtain two sequential numbers from a single generator should be possible.

Avoiding discovery

Each environment will offer its own challenges. If used in cryptography the message will be simply crackable by discovering the primitive and the start point. Just make those as difficult to obtain as the current system of keys and we're done. A message can be encrypted using a primitive and a start point and, so long as those two numbers are sent to the recipient through a different route it is unlikely that the message will be decoded by anyone other than the intended recipient.

In environments such as the card industry where the number is published in its raw form a different approach must be taken. A prime benefit of the system is that each number will be in use for a comparatively short time - perhaps typically not much more than a few minutes. Problems should only arise when someone can predict the sequence and game the system that way. I am confident that issues such as this can be easily avoided - besides, it must be an improvement over someone getting a 16-19 digit number and being able to use that for days or even weeks after for fraudulent withdrawals from someones account.

I have deliberately left out some of the small and subtle tricks that would disguise the sequence from prying eyes.

Powered by Google App Engine