線形合同法 - データサイエンス関連+αのメモ

線形合同法 (linear congruential generator: LCG) は、最も古く、また最もよく知られた擬似乱数生成アルゴリズムの一種。

概要¶

パラメータ $A, C, M$ と変数 $x$ の初期値 $x_0$ のもとで、変数 $x_n$ の漸化式

x_{n+1} = (A \times x_n + C) \operatorname{mod} M

(1)

によって計算される。

生成周期について¶

周期の最大は $M$
以下の条件をすべて満たすと周期が最大になる：
- $C$ と $M$ が互いに素(最大公約数が1)
- $A-1$ が $M$ の全ての素因数で割り切れる
- $M$ が 4 の倍数ならば $A-1$ も 4 の倍数

実装¶

pythonでいうと

x = (A * x + C) % M

で済む。クラスにするなら以下のようになる。

class LCG:

    def __init__(self, A, C, M, x_0):
        self.A = A
        self.C = C
        self.M = M
        self.x = x_0

    def gen(self):
        self.x = (self.A * self.x + self.C) % self.M
        return self.x

random = LCG(A=123, C=456, M=789, x_0=1)

for trial in range(5):
    x = random.gen()
    print(f"{trial}: {x=}")

0: x=579
1: x=663
2: x=738
3: x=495
4: x=588

パラメータを変えて実験¶

# 周期が最大になる例
random = LCG(A=13, C=5, M=12, x_0=0)

# 最大周期を確認するためM+1回繰り返す
for trial in range(random.M + 1):
    x = random.gen()
    print(f"{trial+1}: {x=}")

1: x=5
2: x=10
3: x=3
4: x=8
5: x=1
6: x=6
7: x=11
8: x=4
9: x=9
10: x=2
11: x=7
12: x=0
13: x=5

# 周期が最大にならない例
random = LCG(A=999, C=999, M=999, x_0=1)

for trial in range(5):
    x = random.gen()
    print(f"{trial+1}: {x=}")

1: x=0
2: x=0
3: x=0
4: x=0
5: x=0

問題点¶

割る数 $M$ が偶数の場合、乱数は奇数と偶数が交互で生成される。
→ 次の値が部分的ながら予測できてしまう

なので、LCGは暗号論的擬似乱数生成器ではなく、そのまま暗号に使用してはならない。

random = LCG(A=13, C=5, M=12, x_0=0)

for trial in range(6):
    x = random.gen()
    print(f"{trial+1}: {x=}")

1: x=5
2: x=10
3: x=3
4: x=8
5: x=1
6: x=6

応用例¶

簡易的な乱数生成として用いられる。

良い乱数・悪い乱数によれば、UNIXのrand()やVBAのRnd()などで線形合同法が利用されているらしい。

どのようなパラメータを設定すべきか¶

UNIXのrandの解説にでてきたため有名な例

x_{n+1}=(1103515245 \times x_n + 12345) \bmod 2^{32}

(2)

Park & Miller (1988) が提案した、もっとマシなもの

x_{n+1}= (48271 \times x_n) \bmod (2^{31}-1)

(3)

参考¶

References¶

Park, S. K., & Miller, K. W. (1988). Random number generators: good ones are hard to find. Communications of the ACM, 31(10), 1192–1201. 10.1145/63039.63042