如何使用可逆种子生成所有可能的列表组合?

Question

我想要一个包含100个项目的列表，每个项目的值从0到31不等。然后，我希望能够获取其中一个列表，并知道随机生成该列表所需的种子/输入。

Answer 1

使用合适的线性同余生成器:

你可以使用Pierre L'Ecuyer的研究论文:

Tables_of_linear_congruential_generators_of_different_sizes_and_good_lattice_structure

本文给出的(相当伪随机的)lcg的2模的最低幂为2³⁰，接近10亿。见本文表4。只要选择其中一个lcg，说:

u<子>n + 1 = ((116646453 * u n<子>)+ 5437)国防部2<一口>30

你的每一项正好是5位宽。如果你决定将你的项目6乘6分组，每个组正好是30位宽，所以可以认为是这个模2³⁰LCG的一个状态。

从最初的一组6个项目开始，LCG的一步将产生下一组，即下一个6个项目。论文告诉你，这个系列总体上看起来是相当随机的。

因此，您可以将前6个项目视为您的"种子"，因为您可以从最左边的6个项目重建整个列表。

即使假设为了混淆起见，您在种子之后开始列表的可见部分，您仍然只有大约10亿个可能的种子需要担心。任何一台像样的计算机都能在几秒钟内通过暴力破解找到留下的隐藏种子，通过模拟每个可能种子的LCG并与实际列表进行比较。

示例Python代码:可以从创建一个类开始，给定一个种子，提供0到31之间的无限项:

class LEcuyer30:
def  __init__ (self, seed):
self.seed      = seed & ((1 << 30) - 1)
self.currGroup = self.seed
self.itemCount = 6
def __toNextGroup(self):
nextGroup = ((116646453 * self.currGroup) + 5437) % (1 << 30)
self.currGroup = nextGroup
self.itemCount = 6
def  getItem(self):
if (self.itemCount <= 0):
self.__toNextGroup()
# extract 5 bits:
word = self.currGroup >> (5 * (self.itemCount - 1))
self.itemCount -= 1
return (word & 31)

测试代码:

我们可以创建一个包含20项的序列并输出它:

# Main program:
randomSeed = 514703103
rng = LEcuyer30(randomSeed)
itemList = []
for k in range(20):
item = rng.getItem()
itemList.append(item)
print("itemList = %s" % itemList)

程序输出:

itemList = [15, 10, 27, 15, 23, 31, 1, 10, 5, 15, 16, 8, 4, 16, 24, 31, 7, 5, 8, 19]