为线性同余生成器选择A，C和M

一尘不染

为线性同余生成器选择A，C和M

algorithm

我正在寻找一种简单的伪随机数生成器（PRNG），该生成器具有指定的周期，并保证在该周期内不会发生冲突。经过研究，我发现了非常著名的LCG，它非常完美。问题是，我在理解如何正确配置它方面遇到困难。这是我当前的实现：

    function LCG (state)
    {
        var a = ?;
        var c = ?;
        var m = ?;

        return (a * state + c) % m;
    }

它说，为了使所有种子值都有完整的时间，必须满足以下条件：

c 和 m 是相对质数
a-1* 可被 m的所有素因子整除 *
*如果 *m 是4的倍数，则 a-1 是4 的倍数

1 和 3 很容易理解和测试。但是 2呢，我不太明白这意味着什么或如何检查它。那么C可以为零吗？如果非零怎么办？

总的来说，我需要选择A，C和M，以使我的周期为 48 ^ 5-1 。M等于周期，我不确定A和C。

阅读 520

2020-07-28

共1个答案

一尘不染

从维基百科：

如果 c 不为零，则在且仅在以下情况下，LCG将对所有种子值具有完整的周期：

c 和 m 是相对质数，

a -1可被 m的所有素因子整除，

a -1是4的倍数，如果 m 是4的倍数。

你说你想要一个时期的48 5 -1，所以你必须选择米 ≥48 5 -1。让我们尝试选择 m = 48 5
-1，看看会把我们带到哪里。如果希望周期为 m，那么来自Wikipedia文章的条件将禁止您选择 c = 0 。 __

请注意，11、47、541和911是48 5 -1 的素数，因为它们都是素数，所以11 * 47 * 541 * 911 = 48 5 -1。

让我们经历以下每个条件：

为了使 c 和 m 相对质数， c 和 m 必须没有共同的质因数。因此，选择11、47、541和911 以外的 任何质数，然后将它们相乘以选择 c 。
你需要选择一个这样一个 -1是所有的质因数整除米，即一 = X * 11 * 47 * 541 * 911 + 1对于任何 X 你选择的。
您的 m 不是4的倍数，因此您可以忽略第三个条件。

综上所述：

m = 48 5 -1，
c =除11、47、541和911以外的任何质数乘积（同样， c 必须小于 m ），
对于您选择的任何非负 x ，a = x * 11 * 47 * 541 * 911 + 1 （而且 a 必须小于 m ）。 __

这是一个较小的测试用例（在Python中），使用48 2 -1 的周期（素因数为7和47）：

def lcg(state):
    x = 1
    a = x*7*47 + 1
    c = 100
    m = 48**2 - 1
    return (a * state + c) % m

expected_period = 48**2 - 1
seeds = [5]
for i in range(expected_period):
    seeds.append(lcg(seeds[-1]))
print(len(set(seeds)) == expected_period)

它按需输出True。（如果您在阅读Python时遇到任何麻烦，请告诉我，我可以将其翻译为JavaScript。）

2020-07-28