線形合同法

線形合同法#

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

概要#

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

\[ x_{n+1} = (A \times x_n + C) \operatorname{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) \bmod 2^{32} \]

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

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

参考#