Tech Racho エンジニアの「？」を「！」に。
  1. TOP
  2. Ruby / Rails以外の開発一般
  3. 乱数について本気出して考えてみる
  • Ruby / Rails以外の開発一般

乱数について本気出して考えてみる

プログラミングをやっていると、様々な乱数に出会います。乱数に関しては大勢の研究者が色々な研究結果を出しているため、種類も増え、いったいどれを使えばいいのかと悩む原因にもなります。

大勢が研究し利用している分野ですから、私以外でも大勢が乱数に関する記事を書いているため、あえて新しい記事を書く価値は高くないかもしれません。まあ、既に理解している人はここで記事を閉じるか、暇つぶし程度の感覚で読んでいただくと良いかと思います。

真乱数と疑似乱数

プログラミングの世界の中でいわゆる "乱数" として扱われることが多いのは擬似乱数です。疑似、と付くからには、これは実のところ乱数ではないと言えます。とは言え、擬似乱数を乱数でないと言ってしまうと話が終わってしまうので、疑似乱数を含む乱数を広義の乱数とします。この記事で扱うのは広義の乱数です。逆に、狭義の乱数、本物の乱数は真乱数と言います。

本物と言いましたが、真乱数が良くて疑似乱数が悪い、という訳でもありません。用途によっては、擬似乱数の「疑似」の部分が必要になることもあります。そもそも、コンピューターの世界で疑似乱数が使われることが多いのは、外部からの入力に頼らず、計算だけで真乱数を再現することができないからです。

疑似乱数はともかく、真乱数は以下のような性質を満たす必要があります。

  • 無作為性（randomness）
  • 予測不可能性（unpredictability）
  • 再現不可能性（irreproducibility）

無作為性は、統計的な偏りがなく、規則性もないという性質です。よく疑似乱数の性質を評価する時に、「N次元で均等分布する」という言い方が使われることがありますが、擬似乱数は規則性がないのではなく、規則が複雑なために一見すると相関性がほとんど見えないというのが実際のところです。N次元で均等分布するというのは、少なくともN次元空間に乱数をプロットしても規則性は見えないが、逆に言うとより高次元にプロットすれば規則性が見えてくるということでもあります。
真乱数ならば、Nをどれだけ大きくしても均等分布します。

予測不可能性は、過去に生成された乱数の数列から次に生成する乱数の値を予測できないという性質です。ここで言う予測は、100%である必要はありません。0以上N未満の整数を生成する乱数であれば、当てずっぽうでも1/Nの的中率があるはずですが、十分な試行を繰り返した時に的中率が1/Nからずれるようであれば、予測可能であるとみなせます（勘違いしやすそうなところですが、的中率が当てずっぽうより高い場合はもちろん、低い場合でも「その値が生成されないことを当てずっぽうよりは良く予測できる」という点で予測可能と言えます）。

再現不可能性は、恣意的に特定の数列を出力させることができないという性質です。例えば、真乱数を生成するはずのデバイスが、内部のバグにより、電源を入れ直した直後僅かに0を出力する可能性が高い、といった話であってもこれは再現不可能性を満たしていないことになります。

先程も言ったように、計算だけで真乱数を生成することはできませんから、外部から何らかの乱雑さ(エントロピー)を持ってくる必要があります。時刻やCPUの温度、ノイズなどがエントロピーの一部になります。また、専用のハードウェアを使うこともあります。通信やユーザーの入力なども、場合によっては外部のエントロピーたり得ます。

いずれにせよ、真乱数を作るには何らかのエントロピーが必要で、エントロピーを得る手段は何にしてもある程度は時間がかかります。したがって、真乱数を高速に生成するのは難しく、少なくとも一般的なコンピューターにとってはコストの高い処理ということになります。そして、実際のところ真乱数の性質を全て満たしていなくても用途によっては問題がないので、そういう場合は擬似乱数を使うのが一般的です。

さて、前置きはこれくらいにして、実務的にはどの用途にはどんな乱数を選べば良いのかが一番重要ですよね。そこで、いくつかのユースケースに沿って解説を行いたいと思います。

シミュレーション（モンテカルロ法）

乱数を用いてシミュレーションや数値計算を行うことをモンテカルロ法と言います。例えば、ランダムにいくつも点を打って、円の内側に入る割合と外側に入る割合から円周率を求めることができるという話は有名かと思います。

真乱数は予測や再現が不可能ですが、シミュレーションでは予測可能であっても問題はありませんし、科学研究に利用されることから、再現性はむしろあった方が良いです。もちろん真乱数を使っても、全ての生成された値を記録しておけば再現は出来るのですが、モンテカルロ法は言ってしまえば、とにかく数をこなして統計を取る方法ですから、生成された値を全部保存しておくとデータ量が膨大になってしまいます。疑似乱数であれば内部状態の初期値を保存するだけで再現ができます。
また、試行回数を増やせば増やすほど時間がかかるわけですから、一回の試行にかかる時間もなるべく短くしたいとなれば、高速に生成できる乱数が向いています。

ただし、モンテカルロ法に使う乱数でもっと重要な性質は無作為性です。いくら高速に生成できても偏りが大きければ話になりません。2次元にプロットした時に模様が出来てしまうほどに偏りがあれば、円周率の計算ですら誤差ができてしまいます。
また、回数をこなすことを考えると、周期が長いという性質も必要です。疑似乱数という物は一回生成するごとに内部状態を更新するようになっていますが、内部状態のバリエーションには限りがあります。したがって、更新を繰り返すといつかは内部状態が元に戻ってしまい、そこからまた同じ数列を生成するようになります。そこまでの回数を周期と言います。例えば32bit線形合同法の周期は 2^{32} ですが、当然、内部状態のデータ量が多いほど周期も長くなります（ただし、注意して実装しないといくら大きい内部状態を持っていても周期が短くなってしまうこともあります）

以上のような性質を満たす乱数として、有名なのがメルセンヌ・ツイスタです。メルセンヌ・ツイスタはメルセンヌ素数の性質を利用した乱数で……などと解説を始めても恐らく一部の人以外は興味がないでしょうし、興味がある人は開発者の一人である松本眞さんによる数学者向け説明とかを見るといいと思います。

使われることが多いのはMT19937と呼ばれるものですが、ここでは性質についてざっくりと説明すると、 2^{19937}-1という長周期であり、623次元に均等分布する（言い換えれば、623次元の数が必要なシミュレーションに使っても偏りが生じない）ほどの無作為性があります。

逆に、短所ですが、2^{19937}-1の長周期はそのまま19937ビットの内部状態を必要とすることになります。バイト数で表現するなら2493バイト（19937 \div 8=2492.125を切り上げ）で、これは擬似乱数の内部状態としてはかなり大きい方です。とは言え、UTF-8日本語文字列なら800文字程度、ツイッターで10ツイートもすれば余裕で超えられる情報量ですから、大したこと無いと言ってもいいと思いますが。

また、周期や分布の精度がそこまで必要がないのであれば、もっと速い疑似乱数生成アルゴリズムも存在します。メルセンヌ・ツイスタは性質面では十分良い擬似乱数ですが、場合によってはそれよりも速さを求めた方がいいこともあります。

ちなみにメルセンヌ・ツイスタには改良版としてSFMTという物が存在します。SFMTにはSIMDを利用した高速計算や、 2^{19937} 以外のメルセンヌ素数を利用したより長周期だったり、あるいは逆により軽量だったりするバージョンも用意されています。

UUID生成

以前、10秒で衝突するUUIDの作り方というスライドが話題になり、メルセンヌツイスタはそんなに衝突しないといったアンサー記事も出されていました。

スライドの方は下手な生成方法を使うと衝突するという警句であり、記事の方はスライドそのものよりはそれを見た人の反応に存在する誤解を解くためのものと筆者は理解しています。実のところこの記事の執筆動機もここらへんの話題からです。

UUIDのバージョン4は122ビットの乱数が必要です。
そもそもUUIDの用途を考えると、完全に分散したシステムで、つまり通信による同期なども行わない前提で、可能な限り衝突しないIDという物になります。適切な生成方法さえ取れば衝突の確率は非常に低く、もしそれでも衝突したら、それはきっと個人的な不運を通り越して人類全体がものすごく運が悪かったという話になるでしょう。

では、その適切な生成方法とは何か。
UUID生成に最も重要な性質は再現不可能性です。ものすごく運が悪かった時を除けば、意図せずに発生した衝突は間違いなく乱数が再現してしまったことによるものです。そのため、可能ならば真乱数を利用すれば間違いありません。122ビット分のエントロピーがあればUUIDを一個生成することができます。システムによってはそのためのデバイスを用意してもいいでしょう。

では、UUID生成を行うのが個人用PCで、大量にUUIDを生成するけどそんなにエントロピーが存在しないという場合はどうすればいいか。もちろんそういう場合は擬似乱数を使うことになります。

この時、予測不可能性は満たしている必要はありません。予測できたところで衝突しなければ良いわけです。UUIDはふつう公開情報ですから、衝突させようとすれば簡単です。既に公開されているUUIDと同じ物を使えば衝突しますね。

※2020年6月18日追記：上記の文は当初「予測可能性は満たしている必要はありません」となっていましたが、「予測不可能性」の間違いでした。指摘を受けて修正いたしました。

連続してUUIDを生成する場合、疑似乱数の内部状態が122ビットではさすがに困ります。内部状態の初期化に真乱数を使うとして、122ビットの内部状態が同じになる可能性はUUIDの衝突する可能性と同じく十分に低いですが、連続して生成した時に範囲が重複してしまう可能性まで考えるとそれなりに高くなってしまいます。従って、UUID生成に使う疑似乱数はメルセンヌ・ツイスタなどの内部状態が大きく長周期なものである必要があります。当然その内部状態は真乱数で初期化しないと再現性が生まれてしまう可能性があります。

なお、UUIDに限らず、何らかのIDをランダムに生成する場合は大体同じような考え方が必要です。

暗号通信

暗号通信では、様々な箇所で乱数が必要になります。
例えば、公開鍵暗号の秘密鍵は乱数を利用して生成しますし、TLSの通信中に利用する共通鍵も乱数で生成します。ブロック暗号のパディングも乱数です。

暗号通信で必要になる乱数の性質は基本的に真乱数と同じです。つまり、予測不可能であり、再現不可能であり、無作為である必要があります。

しかし、何度も繰り返すようですが、真乱数は生成コストが高く、特に暗号通信はインターネットに繋がるいかなるデバイスでも必要な処理ですから、なるべく特別な機器を必要とせず、それなりに軽量である必要もあります。
そこで、暗号通信に必要な性質を満たす擬似乱数生成機を暗号論的擬似乱数生成機(CSPRNG)と呼びます。

CSPRNGにも色々なアルゴリズムがありますが、基本的には疑似乱数とエントロピーの一部を合成する仕組みです。つまり、10のエントロピーがあったとして、それをそのまま利用するのではなく、疑似乱数と組み合わせて100の乱数を出力する訳です。もちろん、真乱数と比較すれば一部が疑似乱数由来なので完全に予測不可能になった訳ではありませんが、秘密鍵が破られるほど安全性が低くなければ問題はないと言えます。また、利用する擬似乱数も出来る限り予測不可能性が満たされている必要があり、SHA-1などのハッシュ関数やブロック暗号アルゴリズムを利用して乱数を生成することが多いようです。

CSPRNGにはYarrowアルゴリズムやFortunaアルゴリズムなどがありますが、暗号通信の問題はセキュリティの問題に直結します。今後特定のアルゴリズムに脆弱性が見つかる可能性もないとは言えません。

現代のOSであれば、何らかの形でCSPRNGを提供しているはずですし、あなたがまさにOSにそれを実装する立場でないのなら、特定のアルゴリズムを選ばない方が良いです。Unix系OSなら /dev/random が使えるはずだし、Windowsなら BCryptGenRandom 関数などがあります。基本的には中身を気にせずにそれを利用するべきです。

ゲームにおける乱数

ゲームであれば大抵は何らかの乱数を利用することと思います。パズルゲームやシューティングゲームなど、固定の面をクリアする形式のものであれば不要なこともありますが、カードゲームやサイコロなどを再現する必要があるゲームでは必須ですね。

とは言え、ゲームの場合は科学的な数値計算シミュレーションほどの周期や無作為性が求められる訳でも、暗号化に使うほどの安全性が求められる訳でもありません。

通信を伴わないゲーム

シングルプレイのRPGなど、基本的にスタンドアロンで通信を必要としないゲームでは、人間が違和感を覚えない程度の疑似乱数であれば十分だったりします。実際、昔のゲームなんかだと、リソースやレジスタの大きさの問題もあり、周期が短かったり偏りが大きい疑似乱数が使われていることも少なくありません。だからといって、わざわざ質の悪い疑似乱数を選ぶ必要もありませんが、例えばメルセンヌ・ツイスタだとほとんどの場合オーバースペックなので、もっと速い疑似乱数アルゴリズムを選んだ方が良さそうです。

C言語の rand 関数の実装はほとんどの場合 線形合同法 が利用されています。線形合同法は乗算と加算を使って実装されたアルゴリズムです。一番最初に提唱されたものを見ると下位1ビットで0と1が交互に登場するという偏りがあるため、質の良くない疑似乱数の例として挙げられることもありますが、最近のC言語ライブラリはさすがにそのくらいは対策されているので、特にスタンドアロンで他に影響を与えることのない環境でゲームに使う用途なら問題は大きくなかったりもします。線形合同法は32bitや64bitなど小さい内部状態で実装可能です。

他の有力なアルゴリズムだと、xorshift系の疑似乱数があります。名前の通りxor演算とshift演算を組み合わせたアルゴリズムで、これはどちらも高速に計算可能なので、線形合同法より速いとされています。内部状態の大きさも、バリエーションによりますが32bitから1024bit程度と小さく、線形合同法からこちらに置き換えられることも多いです（例えばブラウザの Math.random 実装は xorshift派生のxoroshiroアルゴリズムに置き換えられています）。

通信を伴うゲーム

クライアント-サーバー方式で通信を行うゲームの場合、一つのサーバーに多数のクライアントが接続し、サーバーが全ての乱数を生成します。

クライアントの接続タイミングは基本的に予測不可能です。従って、十分な数のクライアントが同時接続している場合、そのリクエストはエントロピーと見なすことが可能です。従って、一回のリクエストあたりの乱数生成数が十分に少なければ、周期の短い乱数を使ってもクライアント側には十分な乱雑さがあるように見えることになります。ですので、線形合同法やxorshiftも場合によっては利用可能です。

ただし、これはクライアント側がサーバー側を信頼するという前提に立つ場合です。大抵のネットゲームでは暗黙的にサーバーは信頼される物と考えられますが、場合によってはその信頼性に疑義が出されることがあります。特に、

  • 排出率の低いレアが含まれるガチャ
  • 山の中身が秘匿情報になっている麻雀やトランプゲームの対人戦

といった分野では、サーバーが不正をしていないことを積極的に証明することが求められたりします。

例えばオンライン麻雀の天鳳では牌山ハッシュ値なるものを公開し事後的に検証できるようになっているようです。事前に複数のゲームのための山を生成し、そのハッシュ値を公開することで、事後に検証が可能という理屈のようですが、今回この記事を書くにあたって、そう言えばそんな物もあったなと思い出しただけなので筆者は検証をしたことがありません。機会があればそのうち試してみようかと思います。

ただ、この検証方法も完全ではなく、事前生成した山から改変を加えられていないことは保証できても、そもそも山自体に偏りを加えるようなことは可能です。

任意の数のクライアントとサーバーが通信して、完全に不正を行う余地のない乱数生成を行うには、簡単に言ってしまうと、以下のような手順を行う必要があります（一時的に秘匿する必要がある場合はもう少し複雑になります）

  1. 各クライアントとサーバーがそれぞれ独自に乱数を生成する
  2. 1の乱数を繋げたものからハッシュ値を生成する
  3. 2のハッシュ値を疑似乱数のシードに使う

具体的な通信プロトコルも示してみようかと思ったのですが思った以上にボリュームが増えてしまいそうなので、いずれ別の記事にでもしてみようかと思います。

おまけ1. 疑似乱数の初期化について

疑似乱数を初期化するための値を種（シード）と呼びますが、シードの扱いによっては性質の良い疑似乱数アルゴリズムでもその能力を十全に発揮できなくなってしまうことがあるので注意が必要です。

例えば、C言語の線形合同法だと、内部状態は32bit整数なので、初期化も32bit分の何らかのエントロピーが必要です。
ここを例えば「時刻のミリ秒」などにしてしまうと、これは1000通りしかないので、衝突がしょっちゅう発生してしまうことになります。

また、MT19937は19937bitの内部状態を持ちますが、例えばUnixタイム全体をシードにしたとしても64bit程度しか存在しないため、やはり内部状態に対してシードの状態が少なすぎます。

基本的には、シードは初期化する擬似乱数の内部状態と同じサイズであるべきで、その値は真乱数によって生成すべきです。また、真乱数を直接得ることができない場合は、CSPRNGを使いましょう。

おまけ2. マルチスレッドにおける乱数の扱いについて

CPUの論理スレッド数が多ければ、独立な計算はそれに合わせて複数のアプリケーションスレッドを使ったほうが当然速いです。モンテカルロ法でも当然同じですが、ここで問題になるのが疑似乱数の生成です。

疑似乱数は生成のために内部状態を更新するので、複数のスレッドが同じ内部状態を共有すると、生成の度に排他制御が必要になります。それでは全体の処理速度が疑似乱数生成に律速されてしまうため、マルチスレッドの恩恵が減少してしまいます。かといって、スレッドごとに内部状態を持たせると、場合によっては乱数を生成する範囲が重なってしまい、偏りが生じてしまいかねません。

そこで、そのような場合に要求される擬似乱数の性質としてジャンプの高速さがあります。

任意の内部状態 X について、一回乱数を生成した次の内部状態を f(X) とします。 X から n 回乱数を生成すると

    \[\underbrace{f(f(f(...}_n f(X)...)))\]

となります。これを f^n(X) としましょう。ジャンプは任意の X から f^n(X) を生成する操作です。 n が十分に大きい（ただし乱数の周期よりは十分に小さい）値であれば、 n 回乱数生成するまでジャンプ後と内部状態が被ることがありません。

もちろんこれは n 回乱数生成をすれば可能ですが、それだとシングルスレッドで計算するのと同じなので、ジャンプはそれより速くできる必要があります。

線形合同法のジャンプは行列の冪乗で表すことができます。冪乗の計算が O(\log n) 、行列の適用は O(1) で可能なので、 n 回ジャンプする計算は一度キャッシュを生成すればあとは非常に高速ということになります。

SFMTでは、ジャンプ多項式と呼ばれる式を事前計算することでジャンプを実現しています。ジャンプ多項式がキャッシュに該当する訳ですが、これの計算はそれなりにコストがかかるようです。実行時ではなく事前計算がいいでしょう。

また、XorShiftもキャッシュを計算することでジャンプが実現可能なようです。

ちなみにジャンプの速さで言うと、内部状態は単純にカウンターで、生成時にある計算を通すことで乱雑に見える値を生成するという思想でCBGなる乱数生成機を作っている方がいました。周期はカウンターのビット数依存でこの場合は 2^{64} ですし、分布に関しては検定プログラムは通しているものの、検定を通ることを優先して最適化した（言い換えれば、検定さえ通れば実用上の偏りがあっても良しとした）ようですが、これはジャンプが単純に加算で済むのでキャッシュの生成も必要なく常に O(1) だというのが面白い所ですね。

終わりに

真面目に書き出したら結構なボリュームになってしまいました。とにかく乱数には色々な生成方法があって、適切に扱わないと落とし穴に嵌ることも多いです。気をつけていきましょう。

おたより発掘

関連記事

楕円曲線暗号アルゴリズムを理解する


タグ
この記事を書いた人

yoshi

平成元年生まれのC++er。Qiitaで誰が得するのか分からないような重箱の隅をつつく黒魔術を書いていたが、2016年8月からBPSに入社。

yoshiの書いた記事一覧へ

本記事の内容へのお問い合せはTwitterで@techrachoへMentionまたはDMにてご連絡頂くか、運営会社であるBPS株式会社のお問い合せフォームよりお問い合せ下さい。

CONTACT

TechRachoでは、パートナーシップをご検討いただける方からの
ご連絡をお待ちしております。ぜひお気軽にご意見・ご相談ください。
CONTACT FORM