非常大（10^1.2mil）数的伪随机算法？

Question

我在寻找一个伪随机数发生器（一种算法，你输入一个种子数，它输出一个不同的“随机数”，同一个种子总是产生相同的输出），用于1到95之间的数字^1312000。在

我会使用Linear Feedback Shift Register (LFSR)PRNG，但是如果我这样做了，我就必须把种子数（在以-10为基数的情况下最多可以有120万个数字）转换成一个二进制数，这将是如此巨大，我认为它将花费太长的时间来计算。在

作为对similar question的回应，我们推荐了Feistel密码，但我不了解wiki页面上的词汇表（我要上10年级了，所以我没有加密学位），所以如果你能用外行的术语，我会非常感激的。在

有没有一种有效的方法可以做到这一点，直到时间的尽头，或者这个问题是不可能的？在

编辑：我忘了提珠三角序列需要有一个完整的周期。我的错误。在

Answer 1

一个简单的方法是使用linear congruential generator和模m = 95^1312000组成的linear congruential generator。在

生成器的公式是x_(n+1) = a*x_n + c (mod m)。根据Hull-Dobell定理，当且仅当gcd(m,c) = 1和{}除{}时，它将具有全周期。此外，如果您想要很好的第二个值（就在种子之后），即使对于非常小的种子，a和{}应该相当大。另外，代码不能将这些值存储为文本（它们太大了）。相反，您需要能够可靠地在运行中生成它们。为了确保gcd(m,c) = 1，我尝试了一下：

import random

def get_book(n):
    random.seed(1941) #Borges' Library of Babel was published in 1941
    m = 95**1312000
    a = 1 + 95 * random.randint(1, m//100)
    c = random.randint(1, m - 1) #math.gcd(c,m) = 1
    return (a*n + c) % m

例如：

^{pr2}$

显示“book”编号42的最后100位数字。考虑到Python对大整数的内置支持，代码运行速度惊人地快（在我的机器上抓取一本书只需不到1秒）

Answer 2

如果您有一个可以产生伪随机数字的方法，那么您可以将任意多个连接在一起。它将与基础prng一样具有可重复性。在

但是，如果将内存扩展到数百万位数并尝试进行算术运算，则可能会耗尽内存。通常情况下，这种规模的事情不会在“数字”上完成。它是在字节向量或类似的东西上做的。在