線形合同法

線形合同法#

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

概要#

パラメータ $A, C, M$ と変数 $x$ の初期値 $x_{0}$ のもとで、変数 $x_{n}$ の漸化式

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

によって計算される。

生成周期について#

周期の最大は $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) mod 2^{32}

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

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