今回は疑似乱数の生成方法についてです


解説動画はこちら




乱数と疑似乱数

今回は疑似乱数についてのお話です

一般的に乱数というものは
予測できない数値のことで
原子核の放射崩壊により放出された放射線のカウント
のように予測が出来ない数値のことです

一方で疑似乱数とは
コンピューターで生成した一定の規則に基づく
乱数のような値のことで

真の乱数列は本来、規則性も再現性もないものであるため
本来は確定的な計算によって求めることはできないです

擬似乱数は計算によって作るので
生成法と内部状態が判れば予測も可能ではあります。

また過去に現れた数と同じ数が現れた際のその長さを
周期と言っています。



疑似乱数の作成手法


一般的には初期値（シード）と
演算法（アルゴリズム）を用いて生成します。



平方採中法 (middle-square method)

1946年頃、数学者ノイマンによって提唱された手法です。

この方法は
適当に初期値を決める 例 : 1234
その数を 2 乗した値の中央にある必要な桁数を採って
次の乱数とする

これを繰り返して乱数列とする方法です。

Pythonでの実装例はこんな感じになります。

# ノイマンの平方採中法による乱数生成
def middle_square_method(seed, num_samples=10, num_digits=4):
    random_numbers = []
    current_value = seed
    for _ in range(num_samples):
        num_digits = len(str(current_value))
        # 2乗して中央の桁を取り出す
        squared_value = current_value ** 2
        squared_str = str(squared_value).zfill(2 * num_digits)
        # 中央の桁を取り出す
        start = len(squared_str) - num_digits - 2
        middle_digits = squared_str[start: start + 4]
        current_value = int(middle_digits)
        random_numbers.append(current_value)
    return random_numbers

# 初期値とパラメータ設定
seed = 1234  # 初期値（任意の4桁の数）
random_nums = middle_square_method(seed)
print(random_nums)



線形合同法 (linear congruential method)

次のような漸化式による生成方法です。

スクリーンショット 2025-04-05 17.35.45

周期の最大は m で
パラメータ次第では周期が短くなり
予想ができてしまう手法です。


class LCG:
    def __init__(self, seed=1, a=1664525, c=1013904223, m=2**32):
        self.a = a
        self.c = c
        self.m = m
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state / self.m

# 使用例
seed = 1320
lcg = LCG(seed=seed)
for _ in range(10):
    print(lcg.next())
0.7476371766533703
0.0075369239784777164



Xorshift

George Marsagliaが2003年に提案した手法です

ビット演算を用いた高速な擬似乱数生成法で
基本的な計算ステップは次の3つです。
state ^= (state << a)
state ^= (state >> b)
state ^= (state << c)
a, b, c は定数（一般的には a=13, b=17, c=5）
^= はビット単位の XOR を行って
結果を state に代入です。
class XorShift32:
    def __init__(self, seed=2463534242):
        self.state = seed

    def next(self):
        x = self.state
        x ^= (x << 13) & 0xFFFFFFFF
        x ^= (x >> 17)
        x ^= (x << 5) & 0xFFFFFFFF
        self.state = x & 0xFFFFFFFF
        return self.state / 0xFFFFFFFF

# 使用例
xorshift = XorShift32(seed=123456789)
for _ in range(5):
    print(xorshift.next())
0.6321277193799912
0.5212643641329521


メルセンヌ・ツイスタ (Mersenne Twister : MT)

1996年に松本眞と西村拓士によって
国際会議で発表された手法です。

名前の由来は
周期がメルセンヌ素数（2^19937 - 1）であることからだそうです

•出力：32ビットの整数
•長所：
•非常に長い周期（2^19937 - 1）
•高次元（623次元）でも均一な分布を持つ
•高速（特にビット演算が中心）

以下の3ステップで計算されています。
1.初期化（シードによる状態配列の構築）
2.状態配列の更新（Twist）
3.出力整形（Tempering）


元々Pythonのrandomなどの実装は
この手法を基にしているそうなので
実装する必要は無いのですが
中身の実装を真似るとこんな感じのコードになります
class MT19937:
    # 初期化（シードによる状態配列の構築）
    def __init__(self, seed):
        self.w, self.n, self.m, self.r = 32, 624, 397, 31
        self.a = 0x9908B0DF
        self.u, self.d = 11, 0xFFFFFFFF
        self.s, self.b = 7, 0x9D2C5680
        self.t, self.c = 15, 0xEFC60000
        self.l = 18
        self.f = 1812433253

        self.MT = [0] * self.n
        self.index = self.n
        self.lower_mask = (1 << self.r) - 1
        self.upper_mask = (~self.lower_mask) & 0xFFFFFFFF

        self.MT[0] = seed
        for i in range(1, self.n):
            self.MT[i] = (self.f * (self.MT[i - 1] ^ (self.MT[i - 1] >> (self.w - 2))) + i) & 0xFFFFFFFF

    # 状態配列の更新（Twist）
    # 複数のビットを結合して新しい状態を作り出す処理
    def twist(self):
        for i in range(self.n):
            x = (self.MT[i] & self.upper_mask) + (self.MT[(i + 1) % self.n] & self.lower_mask)
            xA = x >> 1
            if x % 2 != 0:
                xA ^= self.a
            self.MT[i] = self.MT[(i + self.m) % self.n] ^ xA
        self.index = 0

    # 出力整形（Tempering）
    # 出力する前にビットをシャッフルして統計的性質を良くする
    def extract_number(self):
        if self.index >= self.n:
            self.twist()

        y = self.MT[self.index]
        y ^= (y >> self.u) & self.d
        y ^= (y << self.s) & self.b
        y ^= (y << self.t) & self.c
        y ^= (y >> self.l)
        self.index += 1
        return y & 0xFFFFFFFF

    def random(self):
        return self.extract_number() / 0xFFFFFFFF


まとめ

コンピューターでは真の乱数を生成することは
非常に困難ですが乱数に近い値を計算で求める事は出来ます

しかし乱数生成アルゴリズムが分かってしまった場合には
リスクが発生することがあります。


システム内で使用される乱数
（セッションID、認証トークン、パスワードのハッシュなど）が
予測されて攻撃されたり

暗号化や認証に使用される乱数
（例：暗号鍵生成やトークンの生成）が
予測可能だと、暗号が破られやすくなるでしょう。

またゲームやギャンブルサイトでの
不正行為にも使われてしまった例があったようです。

まあ、疑似乱数を1から生成するコードを実装する機会は
ほとんど無いかもしれませんが、アルゴリズムの採択によっては
それがシステム上のリスクになりえる事は
考えておいても良いんじゃ無いでしょうか

今回は疑似乱数についてのお話でした。
それでは。


タグ ：
#Python
#プログラミング
#疑似乱数
#メルセンヌツイスタ