需要一个生成序列号的算法。

Question

我想生成一个16位十六进制序列号，例如：F204-8BE2-17A2-CFF3。（这个模式可以给我 16^16 种不同的序列号，但我并不需要它们全部。）

我需要你们都建议一个算法，以随机方式生成这些序列号，并具有特殊特征：每两个序列号之间至少有6个不同的数字。 （=如果你得到了两个最相似的序列号，它们仍然应该在6个索引处有差异。）

我知道一个具有这种特征的好算法需要记住先前生成的序列号，但我不需要那么多。

事实上，我需要一个算法，在选择一对碰撞（少于0.001）的概率最小的情况下进行运算足够了。 PS:
我刚刚试图使用MD5哈希随机创建10K个字符串，结果出现了相似的字符串（相似=超过3个相同的数字）概率为0.00018。

- Emadpres

---

具有最小坏序列号概率（小于0.001似乎足够）取决于您需要的序列号数量。如果您需要16 ^ 16 + 1个序列号，那么您肯定会至少有一个完整的碰撞。 - Niklas B.

我需要最多1M个序列号，这比16的16次方要少得多。 - Emadpres

0.001 概率是什么意思？是指所选对碰撞的概率，还是指存在某些对发生碰撞的概率？ - Niklas B.

@NiklasB. 选定一对碰撞的概率。 - Emadpres

那么你可以直接采用朴素方法（参见我的答案）来处理。 - Niklas B.

Answer 1

可以构建一个正确的生成器，而不必记住所有先前生成的代码。您可以使用海明码生成间隔6个字符的序列号。可以设计一种海明码来任意间隔两个不同的生成值。显然，距离越大，您将不得不使用更高的冗余度，导致更复杂的代码和更长的数字。

首先，您可以根据自己的喜好设计海明码，将数字编码为十六进制数字序列，然后可以取任何数字序列并将其用作种子，例如质数。您只需要始终记住上次使用的数字并使用下一个数字即可。

话虽如此，如果您不需要确保两个序列之间的最小距离，并且可以容忍一定的误差，我建议使用任何半好的哈希函数或密码应该会产生相当分散的输出。因此，我首先尝试使用MD5或SHA哈希在1-1000的数字上进行测试。我希望结果会相当令人满意。

- Warlord

Answer 2

我建议您研究一下 ANSI X9.17 伪随机比特生成器。这些幻灯片中给出了算法草图。ANSI X9.17 生成64位伪随机字符串，这正是您想要的。

经过NIST批准的修订和增强版本的生成器，请查看此页面。

现在，无论您使用 ANSI X9.17 生成器、另一个生成器还是开发自己的生成器，都最好让生成器通过一些统计测试，以确保其伪随机比特的质量。

示例测试包括ENT电池、DIEHARD电池和NIST电池。

- user2845946

---

好的。我也会测试这个。 - Emadpres