如何在不预先生成整个序列的情况下生成序列的可预测混洗？

Question

以下python代码准确描述了我想要为任意大小(填充)序列实现的目标:

import random
fixed_seed = 1 #generate the same sequence every time with a fixed seed
population = 1000
sample_count = 5 #demonstration number
num_retries = 3  #just enough to show the repeatable behaviour
for trynum in xrange(num_retries):
    #generate the fresh/ordered sequence (0->population)...
    seq = range(population)
    #seed the random number generator the same way every time...
    random.seed(fixed_seed)
    #shuffle the sequence...
    random.shuffle(seq)
    #display results for this try...
    sample_sequence = [str(x) for x in seq[:sample_count]]
    print "try %s: %s..." % (trynum + 1, ", ".join(sample_sequence))
#Sample output...
#try 1: 995, 721, 62, 326, 541...
#try 2: 995, 721, 62, 326, 541...
#try 3: 995, 721, 62, 326, 541...

该方法的问题在于它需要首先在内存中生成整个序列.对于庞大的人群来说,这可能是个问题.

请注意,此方法的一个潜在巨大优势是您可以随时选择任何阵列位置.

现在 - 如果手头的问题恰好让您将总体大小设置为2的幂(减1),则可以使用线性反馈移位寄存器来获得可预测的随机序列.LFSR很简洁,并且在维基百科的文章中对它们进行了很好的解释.

下面的python代码演示了这一点(我做了一堆唯一性测试,以确保它像宣传的那样工作).再次查看维基百科文章,了解代码的工作原理(Galois配置).

TAP_MASKS = { #only one needed, but I included 3 to make the code more useful
    10: 0x00000240, #taps at 10, 7
    16: 0x0000B400, #taps at 16, 14, 13, 11
    32: 0xE0000200, #taps at 32, 31, 30, 10
}

def MaxLengthLFSR(seed, register_length):
    "Gets next value from seed in max-length LFSR using Galois configuration."
    lsb = seed & 1
    next_val = seed >> 1
    if lsb == 1:
        mask = TAP_MASKS[register_length]
        next_val ^= mask
    return next_val

reglen = 16  #number of bits in register
population = (2**reglen) - 1 #not used, just showing it
fixed_seed = 1   #seed == startval in this case (could randomize in population)
sample_count = 5 #demonstration number
num_retries = 3  #just enough to show the repeatable behaviour
for trynum in xrange(num_retries):
    next_val = fixed_seed
    seq = [fixed_seed, ]
    for x in xrange(sample_count - 1):
        next_val = MaxLengthLFSR(next_val, reglen)
        seq.append(next_val)
    seq = [str(x) for x in seq]
    print "try %s: %s..." % (trynum + 1, ", ".join(seq))
#Sample output...
#try 1: 1, 46080, 23040, 11520, 5760...
#try 2: 1, 46080, 23040, 11520, 5760...
#try 3: 1, 46080, 23040, 11520, 5760...

这很好,因为你可以拥有一个巨大的数量,并且可以轻松计算一个可重复的非重复随机数序列,而无需使用大块内存.

缺点是a)它被限制为大小(2**N-1)的"混洗"序列,并且b)你无法确定随机序列中特定位置的值是在任意位置.您需要知道特定点的值并从那里走序列.

后者(b)大部分都可以,因为大多数情况下你会按顺序生成序列,所以你只需要记住最后一个值.2限制(a)的力量是一种交易杀手,但......取决于应用程序.

对于任意序列长度,如何实现最大长度-LFSR类非重复结果？

作为奖励,最好有一个解决方案,让您能够知道给定序列位置的数字,而无需遍历序列到该位置.

---

注意:如果你想要一个良好的起始LFSR分接头位置用于最大长度LFSR(产生整个寄存器数量而不重复一次),这个链接非常好,每个寄存器大小有很多分接位置(最多32位,无论如何).

另请注意,我已经看到许多与我的问题和改组/ LFSR密切相关的问题,但它们都没有完全与我所追求的相关(任意大小的线性序列的可预测的随机播放).或者至少就我能够理解它们而言,无论如何.

我最近一直在研究线性同步发生器,它似乎很有前景,但我还没能让它们工作.我不会再问这个问题,而是如果我弄明白并且他们工作的话就发布答案.

Answer 1

事实上，我之前已经写过相关文章：Secure Permutations with Block Ciphers。简而言之：

1. 是的，您可以使用 LFSR 生成长度为 2 的幂的排列。您还可以使用任何分组密码。使用分组密码，您还可以找到索引 n 处的元素，或元素 n 的索引。
2. 要生成任意长度 l 的排列，请创建一个长度大于 l 的最小 2 次方排列。当你想找到第n个排列元素时，应用排列函数，如果它生成的数字超出了所需范围，则再次应用；重复直到数字在可接受的范围内。

步骤2所需的迭代次数平均不超过2次；最坏的情况发生的概率很高，但极不可能发生。