Need an Algorithm to generate Serialnumber

Question

I want to generate 16-digits hexadecimal serial-number like: F204-8BE2-17A2-CFF3.

(This pattern give me 16^16 distinct serial-number But I don't need all of them)

I need you all to suggest me an algorithm to generate these serial-numbers randomly with an special characteristic which is: each two serial-numbers have (at-least) 6 different digits

(= It means if you are given two most similar serial-number, they should still have difference in 6 indexes)

I know that a good algorithm with this characteristic needs to remember previously generated serial-numbers and I don't want that much.

In fact, I need an algorithm which do this with least probability for a chosen pair to collide (less than 0.001 seems sufficient )

PS:
I've just tried to create 10K string randomly using MD5 hash and It gave similar string( similar=more than 3 same digits) with 0.00018 probability.

Answer 1

It is possible to construct a correct generator without having to remember all previously generated codes. You can generate serial numbers that are spaced 6 characters apart by using Hamming code. A hamming code can be designed to arbitrarily space out two distinct generated values. Obviously, the greater the distance, the higher redundancy you will have to use, resulting in more complex code and longer numbers.

First you design a hamming code to your liking, that encodes a number into a sequence of hexadecimal digits and then you can take any sequence of numbers and use it as a seed, such as prime numbers. You just always need to remember, what number was used last and use the next one.

That being said, if you don't need to properly ensure minimal distance of two serials, and would settle for a small error, I would suggest that any half decent hash function or cypher should produce decently spaced out outputs. Therefore the first thing I would try to do is to take MD5 or SHA hashes and test-drive them on numbers 1 - 1000. My hopes are, the results will be quite satisfactory.

Answer 2

I suggest you look into the ANSI X9.17 pseudorandom bit generator. An algorithmic sketch is given in these slides. ANSI X9.17 generates 64-bit pseudorandom strings which is what you want.

A revised and enhanced version of this generator was approved by NIST. Please have a look at this page.

Now whether you use ANSI X9.17 generator, another generator, or develop your own, it's a good idea to have the generator pass some statistical tests in order to ensure the quality of its pseudorandom bits.

Example tests include the ENT battery, the DIEHARD battery, and the NIST battery.