The actual maths behind the sequence is not very complicated.
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.
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.
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).
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).
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.
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.
