コンピューターの「ランダム」は本当にランダムなのか？

こんにちは、R&D事業部のチャンウクです。
今回の全研ブログでは、コンピューターの面白い特徴について話をします。

■ 概要

数年前、開発中のシステムのテストを行った際、ランダムなデータが必要になりました。
PHPのランダム関数rand()を使ってテストデータを生成した結果、生成されたデータにパターンが生じてしまい困ったことがあります。

ランダム関数なのに？
コンピューターのランダムって、本当にランダムなのでしょうか？

・
・
・例えば、皆さんは音楽プレーヤーで音楽を聞いています。
ランダム再生ボタンを押したのに、なぜか順序があり、同じパターンで再生されるように感じられたことありませんか？
この曲の次はあの曲…と、耳慣れていることがないでしょうか。

・
・
・また、モバイルゲームをするとき、ガチャを回しています。
なぜか毎回同じアイテムしか出ません。

アイテムプールが決まっているように感じられます。
欲しいアイテムのため、課金もしてみましたがやっぱり出てません。

そもそも欲しいアイテムは、候補の中に存在していないのでは？

・
・
・今年2月、とある宝くじでのトラブルが話題になりました。
ランダム番号生成システムで、10＾32確率の、全く同じ番号が出てしまった不思議な事件です。
なぜこんなことがおきてしまったのでしょうか。

世の中の「ランダム」は、本当にランダムになっているのでしょうか？
分析してみましょう。

■ 「ランダム」とは何か

はじめに、「ランダム」という言葉の意味をはっきりさせましょう。

一般には、「無作為」という意味で使われています。
冒頭であげた、音楽プレーヤーやゲームなどの例を見てわかると思いますが、ソフトウェアを開発するときには、ランダム要素は必須条件で、必要性はものすごく高いです。

コンピューターでは、ランダムな状況を作るため乱数（random_number）を使用します。
乱数は特定の規則がない、無作為に羅列されている数、予測ができない数を意味します。

コンピューターはこの乱数による分岐で、実行するコード、出力するデータを決めてランダムを表現しているのです。

■ コンピューターのランダムは本当にランダムなのか

しかしdeterministic machine（決定論的な機械）であるコンピューターは、基本的に無作為を作ることができません。
computerは入力値をcomputing（計算）して結果を出力しますが、計算された数字をランダム（無作為）と呼ぶのは違和感がありますよね。

考える能力がなく、入力値がないと何もできないコンピューターが、どのようにランダムを作っているのでしょうか。

答えは、「擬似ランダム関数」です。
コンピューターは擬似ランダム関数を使います。

擬似ランダム関数とは、人がソフトウェアとして定義し、コンピューター、プログラミング言語に実装したもので、入力値を入れるとある計算式により乱数を出力してくれる関数です。
現在使われるほとんどのランダム、乱数体系はこの擬似ランダム関数を基盤にしています。

例えば、2468…の数列があったとしたら、「8の次は10がでる。n = 2n」という数式が予測できるため、乱数とは呼びません。

また3333…も同じです。「3が連続する。1/3の小数部」と、規則がすぐ予想されるからです。
285714285714285714…は？パッと見たら乱数かと思うかもしれませんが、よく見てみると285714の繰り返しになっています。ここには、「2/7の小数部」という規則が隠れています。

では、1074113856068743286788995703504…はいかがでしょうか
これは乱数だと思いますか。どんな規則がありそうですか。

ランダムのように見えますが、実は「10000/931の小数部」から出た結果です。

このように、【特定の規則や数式を使ってランダムのように見える数たちを作る】のが、擬似ランダム関数、コンピューターでの乱数生成方法です。

先程から申し上げているように、擬似ランダム関数は関数（Function）の一種なので、必ずInputが必要です。
数式を適用する引数が必要になるため、SEED値を入力しなければなりません。

一般的に使われる擬似乱数のアルゴリズムは、

【Linear Congruential-線形合同法】
https://ja.wikipedia.org/wiki/線形合同法

【Mersenne Twister-メルセンヌ・ツイスタ】
https://ja.wikipedia.org/wiki/メルセンヌ・ツイスタ

・・・など色々ありますが、

いずれも
———————————————————–
最初のSEED値を使って第一ランダム数を取得
→第一ランダム数で第二ランダム数を取得
→第二ランダム数で第三ランダム数を取得…
———————————————————–
のような漸化式の形になっています。

ここでdeterministic machine（決定論的な機械＝コンピューター）の特徴である、「入力が一緒なら出力も一緒」に則り、最初に設定したSEED値が同じなら、出力される乱数も一緒になってしまうことがわかります。

簡単なテストで証明してみましょう。

PHPで作成した、Mersenne Twisterアルゴリズムを採用しているmt_rand（）を使う簡単なテストプログラムです。

▲乱数が20個生成されました。

▲SEED値「0」の同じコードを何度実行しても、同じ配列の数字が出力されます。

▲SEED値は左から「1」「2」「3」。値を変えたことでランダムのように見える値が出力されます。

これでランダム関数は、SEED値を加工しながら値を算出することが確認できます。

PHPは、実は4.2 Version、およそ12年前から micro second、process id など予測しにくいデータの組み合わせで、ランダム関数のSEED値を自動設定してくれているので、わざわざSEED値を設定する必要がなくなっています。
結果を予測するのが難しいのは、PHPスクリプトを実行するとき、自動でこのSEED値を付与するからです。

ランダムについて、ご理解いただけましたでしょうか。

■ 本当のランダムは生成できないのか

SEED値を毎回変えたとしても、究極なランダムとは言えないことが分かったと思います。
数式で決定される値なので、いつかはパターンが見つかり、規則性が発生するということです。
同じSEED値から変換された乱数を収集することで、正確な数式を追跡することも可能です。

実際、例で使ったmt_rand()で生成された乱数は、600個収集すると、これから生成される乱数を全て予測できるそうです。

擬似ランダムで作った乱数は簡単なプログラムには適切ですが、暗号学的には安全ではないので使用に十分注意が必要です。

予測ができない、本物のランダムを作るには、以下の方法があります。

①システムのインタラプト信号を利用した/dev/random
（デバイスドライバなどの情報源から集めた環境ノイズを利用して、真の乱数性を得る）

②従来のコンピューターではなく、量子コンピューターを用いた量子乱数
（量子物理学を用いる）

これらを利用すれば、暗号学的に完全な乱数が作られるので安心して使えます。

■ まとめ

「コンピューターから作ったランダムは、実はランダムではなかった」ことを認識した上で、世の中を見てみましょう。

今まで経験したランダムはランダムではないかもしれません。

いかがでしたでしょうか？
少しでも面白いと思った方は、ぜひR&D事業部に遊びに来てください。