乱数生成ツール

数値はどこから来るのか

抽選にはブラウザの暗号学的に安全な乱数生成器であるcrypto.getRandomValuesを使っています。OSが集めたエントロピーから初期化され、出力を観察しても次に何が出るかについて役立つ情報が一切得られないよう設計されています。

すぐ思いつく代わりのMath.randomは、別種のものです。速度を重視して作られた高速な疑似乱数生成器（典型的にはxorshift128+）で、時計の状態のようなものから初期化され、内部状態が小さいため、いくつかの出力からそれを復元して残りを予測できてしまうこともあります。ECMAScriptの仕様は、暗号目的に使ってはならないとはっきり書いています。

抽選会の当選者を選ぶくらいなら、この違いが問題になることはまずありません。それでもここで使っているのは、コストがかからないからであり、ときどきしか信頼できない生成器は、常に信頼できる生成器よりも扱いを考えるのが難しいからです。

剰余による偏り

乱数を範囲に収める簡単な方法は、範囲の大きさで剰余を取ることですが、範囲が生成器の値域をきれいに割り切れない場合、これは微妙に間違っています。

0〜255のランダムな1バイトから、1〜10の数を求めるとします。バイト値は256通り、答えは10通りで、256は10の倍数ではありません。10個の答えのうち6個には26通りのバイト値が対応し、残りの4個には25通りしか対応しないので、最初の6個は残りより約4%出やすくなります。範囲が1〜100なら偏りはもっと大きく、1〜200ならさらに大きくなります。

対策は棄却サンプリングです。生成器の値域の上端で偏りの原因になる値がいくつあるかを計算し、そこに当たった抽選は捨ててやり直します。ここでは、範囲のちょうどの倍数のうち最大のものを超える値は、折り返して使うのではなく捨てています。ときどき余分な抽選が必要になりますが、範囲内のすべての数の出る確率が完全に等しくなります。このサイトのパスワード生成とUUID生成も、同じ処理を土台にしています。

重複なしで抽選する

重複なしモードは非復元抽出を行います。宝くじの番号、景品の抽選、リストからランダムに一部を選ぶときに使うものです。一度出た値はプールから取り除かれるので、1回の結果の中で同じ数が2回出ることはありません。

そのためには、範囲に含まれる値の数が求めた個数以上である必要があります。4つしかない範囲から6つの異なる数は出せません。その場合、このツールは無限にループするのではなく、そう伝えます。これが制約するのは集合であって順序ではない点に注意してください。数はランダムな順序で抽選されるので、結果は並べ替えたサンプルではなく、ランダムな部分集合をシャッフルしたものになります。順番に並べたい場合は、別途並べ替えを使えます。

向いていない用途

抽選会、サイコロ、テスト用のデータ、どのタスクから手を付けるかの決定など、人が偶然に任せる数多くの小さな判断には向いた道具です。

鍵、パスワード、トークンの生成には向いていません。乱数の質が足りないからではなく、それらには特定の長さと文字種が必要だからです。その用途にはパスワード生成ツールを使ってください。また、参加者が結果を信頼しなければならない公開抽選にも適していません。ページに表示された数字は、それが現れる瞬間を見ていなかった人には何も証明しません。検証可能な抽選には、公開されたシードと抽選前のコミットメントが必要で、まったく別の設計になります。

疑似乱数、暗号論的乱数、そして真の乱数

疑似乱数生成器は決定論的な関数です。開始状態が同じなら、生成される数列は永遠に同じになります。再現性が重要なシミュレーションではこれは長所ですが、次の値を予測しようとする相手がいる場面では弱点になります。JavaScriptのMath.randomはたいていxorshift128+で、高速な代わりに内部状態が小さく、出力を数個集めるだけで復元できてしまいます。

暗号論的に安全な生成器は、出力をどれだけ観測しても残りについて有用な情報が得られないように作られています。シードにはOSが集めたエントロピー、つまりタイミングのゆらぎ、割り込みのパターン、RDRANDのようなハードウェア命令が使われ、定期的に再シードされます。ブラウザのcrypto.getRandomValuesとUnixの/dev/urandomが一般的なインターフェースで、どちらも十分に高速なので、安全性は実質的にコストなしで手に入ります。

熱雑音や放射性崩壊といった物理現象に由来する真の乱数は、専用のハードウェアモジュールやrandom.orgのようなサービスとして存在します。ただし、ほとんどの用途では必要ありません。適切にシードされた暗号論的生成器は、現実に実行できるどんな検定でも真の乱数と区別がつかないからです。

偏りを生まないシャッフルの仕方

直感的なシャッフル、つまり乱数を返す比較関数でソートする方法は誤りで、しかもざっと見ただけでは気づけない形で誤っています。比較ソートは順序が一貫していることを前提にしているため、ランダムな比較関数を渡すと特定の並びに大きく偏った分布になり、結果はソートの実装によっても変わります。シャッフルされたように見えて、実際にはされていないのです。

正しいアルゴリズムはFisher-Yatesです。リストの末尾から順にたどり、各位置についてゼロからその位置まで（その位置を含む）の範囲でランダムなインデックスを選び、交換します。すべての順列が等しい確率で現れ、計算量は線形です。ほとんどの言語の標準ライブラリに正しい実装があり、なければループ4行で書けます。

一部だけを選ぶ場合も、同じ操作を途中で止めるだけです。先頭k個の位置までシャッフルして、それを取り出します。ランダムなインデックスを引いて重複を捨てるやり方でも動きますが、kがリストの長さに近づくと著しく効率が落ちます。ちょうどその辺りから、間に合わせの実装は目に見えて長くループし始めます。

本物のランダムな並びはどう見えるか

人はランダムさを判定するのが苦手で、しかも間違え方は一方向に偏っています。実際のランダムなデータには、直感が許すよりもはるかに多くのかたまりが現れます。コインを100回投げれば、表が6回や7回続くのは不審なことではなくむしろ起こりやすいことで、長い連続がまったくない並びのほうが、人が作り上げた可能性が高いのです。

ストリーミングサービスの音楽シャッフル機能がたいてい本当のランダムではないのは、このためです。本物のシャッフルでは同じアーティストが3回続けて流れることが十分な頻度で起こり、ユーザーから不具合として報告されてしまいます。そこでアルゴリズムは意図的にアーティストを散らします。ランダムさは下がりますが、人がシャッフルという言葉で思い描くものには近づきます。

抗っておきたい関連する直感が2つあります。ひとつはギャンブラーの誤謬で、反対の結果が続いたあとにそろそろ出るはずだと考えてしまうこと。もうひとつは誕生日効果で、衝突が予想よりずっと起こりやすいというもので、23人いれば誕生日が一致する確率は五分五分になります。どちらも、ランダムさがどれだけかたまりやすいかを見誤る、同じ勘違いから生じています。

毎回同じ数列がほしいとき

シミュレーション、手続き的に生成されるコンテンツ、統計的な作業は、いずれも再現性を必要とします。同じシードから同じ数列が得られるからこそ、結果を検証し直し、バグを再現できるのです。暗号論的生成器は意図的にシードを与えられないので、ここではまさに使ってはいけない道具です。

一般的なやり方は、小さくよく検証された疑似乱数生成器、たとえばPCGやxoshiro、古いコードならメルセンヌ・ツイスタを明示的にシードし、そのシードを記録しておくことです。テストでは失敗時にシードを出力しておくだけで、たまにしか起きない失敗が再現可能な失敗に変わります。これが、修正されるバグと誰かに無効化されるテストとの分かれ目になります。

2種類の生成器は分けて管理し、シード付きのものがセキュリティに関わるコードへ紛れ込まないようにしてください。問題になるのは、テストデータのシャッフルとトークン生成の両方に同じユーティリティ関数を使ってしまうパターンです。その瞬間から、決定論的な数列が本来守ってはいけないものを守ることになります。

公正だと納得してもらえる抽選にする

公正さには2つの側面があります。仕組みと、その証拠です。ここでの仕組みは健全で、暗号論的な乱数源と棄却サンプリングを使っているため、範囲内のどの値も等しい確率で選ばれます。一方、証拠のほうはこのページでは用意できません。画面に数字が現れても、それを見ていなかった人にとっては何の証明にもならないからです。

抽選に金銭や義務が絡む場合の定石はコミット・アンド・リビールです。応募を締め切る前に応募者一覧とシードのハッシュを公開し、締め切り後に公開された方法で抽選を行い、シードを公表して誰でも結果を再計算できるようにします。これによって、主催者への信頼が、誰でも確かめられる計算に置き換わります。

日常的な場面、たとえば誰が最初に発表するか、どのタスクから始めるか、最後の1枚のチケットを誰が受け取るかといった場合には、そこまでは必要ありません。ここで意味を持つ公正さは、その場にいる全員が同じ結果を同時に目にできることです。だからこそ、誰かが自分の画面で見た数字を読み上げるより、みんなに見える形での抽選のほうが優れているのです。