Mersenne Twister（MT19937）の仕組み：周期・再現性と暗号に使えない理由

原論文の著者はMakoto MatsumotoとTakuji Nishimura。公開原稿では松本の所属に慶應義塾大学／Max-Planck-Institut für Mathematik、西村の所属に慶應義塾大学が記されています。現在の広島大学ドメインの配布ページから、1998年当時も「広島大学発」とは判断できません。

著者の解説は開発を1996〜1997年、初期化の改良を2002年としています。1998年のアルゴリズムと、2002年版の初期化コードは区別します。名称のMersenneはメルセンヌ素数に関係する周期、Twisterはtwisted GFSR型の状態更新に由来します。

PRNGは内部状態から次の状態と出力を決定します。同じアルゴリズム、初期化方式、seed、呼出順なら同じ系列を再現できます。ただし、seedだけが同じでも異なる言語やAPIで同じ値が出るとは限りません。

物理的なノイズなどから得るエントロピーと、それを種にして値を展開する生成器は別の層です。暗号学的疑似乱数生成器（CSPRNG）も決定的な処理を含みますが、適切な種と設計の下で出力の予測を困難にします。「決定的だからすべて暗号に使えない」わけではなく、MT19937が暗号向けの設計ではない点が重要です。

IntelのRDRANDも物理ノイズをそのまま返す命令ではなく、DRBGの出力を返します。OSやCPUの乱数APIを、無加工の「真の乱数」と一括りにはできません。

長い周期は系列が繰り返すまでの長さです。すべての初期状態を短いseedから選べるという意味でも、隣り合う値が独立である証明でもありません。PHPのMt19937のように32ビットseedを使うAPIでは、周期が巨大でも選択できる系列はそのseed空間に制約されます。

MT19937の623次元等分布は32ビット精度についての性質です。連続623個の32ビット出力を組にし、開始位置を全周期にわたって動かすと、各ビットパターンは同じ回数現れます。ただし全ゼロの組だけは1回少なくなります。これは原論文の定義に含まれる例外です。

精度vビットに切り詰める場合は等分布次元k(v)を別に考えます。「1ビットから623次元まで」という説明では、ビット精度と次元を混同してしまいます。

この性質は短い標本で各結果が同数になる保証ではなく、あらゆる統計検定に合格する保証でも、暗号学的な予測不能性の保証でもありません。Fisher–Yatesが必要とする各段階の条件付き一様選択とも区別してください。

状態更新では、隣接する語の上位1ビットと下位31ビットを結合し、右シフトと条件付きXOR、397語のずれを使います。temperingは出力語へシフトとマスク付きXORを適用する変換です。暗号化ではなく、可逆なビット変換です。

次の学習用コードは2002年版の単一32ビットseed初期化を使います。整数演算は2³²を法とし、JavaScriptでは乗算の下位32ビットをMath.imul、符号なし右シフトを>>>で明示します。twistは配列を順番に上書きし、折り返し後は更新済みの語も参照します。旧配列を別配列へ一括変換する処理に置き換えると系列が変わります。

function mt19937(seed) {
  if (!Number.isInteger(seed) || seed < 0 || seed > 0xffffffff) {
    throw new RangeError("seedは0から2^32-1の整数にしてください");
  }
  const state = new Uint32Array(624);
  state[0] = seed;
  for (let i = 1; i < 624; i++) {
    const previous = state[i - 1];
    state[i] = (Math.imul(1812433253, previous ^ (previous >>> 30)) + i) >>> 0;
  }
  let cursor = 624;
  return function nextUint32() {
    if (cursor === 624) {
      for (let i = 0; i < 624; i++) {
        const joined = (state[i] & 0x80000000) | (state[(i + 1) % 624] & 0x7fffffff);
        state[i] = (state[(i + 397) % 624] ^ (joined >>> 1) ^
          ((joined & 1) ? 0x9908b0df : 0)) >>> 0;
      }
      cursor = 0;
    }
    let value = state[cursor++];
    value ^= value >>> 11;
    value ^= (value << 7) & 0x9d2c5680;
    value ^= (value << 15) & 0xefc60000;
    return (value ^ (value >>> 18)) >>> 0;
  };
}
const next = mt19937(5489);
console.log(Array.from({ length: 5 }, () => next()));
// [3499211612, 581869302, 3890346734, 3586334585, 545404204]

最初の出力前と、624個を使い切った後に次のブロックを更新します。配列は各生成器に独立し、呼び出すたびに32ビット符号なし整数を返します。これは教育用実装であり、暗号用の生成器でも、全言語のseed規則と互換な実装でもありません。

再現性の記録には、生成器の種類・ライブラリと版・seedまたは保存状態・呼出順・範囲や分布への変換方法が必要です。整数一つ、浮動小数点一つ、正規分布一つが同じ数の内部出力を使うとは限りません。

この例のseed 5489とPythonのrandom.seed(5489)が同じ系列になると期待してはいけません。初期化方式が違うためです。並列処理では各workerに同じseedを渡しても独立した系列にはなりません。利用するライブラリのstream分割やspawnの契約を確認します。

出力を単純にnで割った余りで整数範囲へ変換すると、2³²がnで割り切れない場合に偏りが生じます。MTを選ぶだけではこの偏りは直りません。範囲変換と生成器の品質は別々に検証します。

採用されていることと、特定用途で最良であることは同義ではありません。現在のExcel全版や非公開の内部実装を、過去の説明だけで断定することも避けます。

MT19937は暗号学的に安全ではありません。状態更新が線形で、temperingも可逆なため、状態が分かれば後続出力を計算できます。例えば、更新ブロック境界に対応する連続624語の完全な32ビット出力が得られる場合、temperingを逆変換して状態を再構成できます。

「624回観測すれば常に破れる」という無条件な主張ではありません。範囲を絞った整数、複数語を組み合わせた浮動小数点、出力の欠落、別処理による状態更新では観測条件が違います。一方、これらの加工をMTの安全性の根拠にはできません。

パスワード・秘密のトークン・鍵にはブラウザのcrypto.getRandomValues()、Node.jsのcrypto.randomBytes()、Pythonのsecrets、PHPのrandom_bytes()など、用途に合う暗号用APIを使います。nonceに必要なのが一意性か予測不能性かはプロトコルに従い、MTで両方を自動的に満たせるとは考えません。

Web Cryptoは暗号学的に強い乱数を要求しますが内部方式を固定しません。取得失敗時にMath.random()へ黙って置き換えると、秘密値の契約を壊します。

SFMTはSIMDを意識したMT系の生成器で、PCGやxoshiro系などにも異なる設計上の選択があります。これらを一つの「後継」として順位付けすることはできません。

比較には対象CPU、コンパイラ、整数幅、分布変換、並列stream、統計テスト、再現性、暗号要件を揃えます。条件のない「2.5倍速」や「世界最高品質」という数字や順位は意味を持ちません。高速な非暗号PRNGへ替えても、暗号用の安全性が得られるわけではありません。

本サイトのランダム系ツールの実装を整理:

各ツールの乱数源と割り当て方法は上表の実装説明を確認してください。Web Crypto APIの採用だけで、物理抽選との同一性、第三者監査済みの公平性、くじ・賭け等の法的要件が保証されるわけではありません。

ECMAScriptのMath.random()の具体的な方式は実装依存です。Web CryptoもMTを指定していません。上表は現在のNanToo日本語ツールの説明であり、このページの学習用MTコードを本サイトのツールへ組み込んでいるわけではありません。

生成器は値の系列を作り、Fisher–Yatesは選択値を使って並べ替えます。確率計算はさらに別で、理想化した独立・一様なサイコロの分布を数学で求めます。ダイス確率計算機や3d6と4d6-drop-lowestの記事の分布を、MT固有の出力保証とは混同しないでください。

用途から選ぶのが基本です。再現可能な実験には記録可能なPRNG、安全な秘密値にはCSPRNG、公平な範囲割当には適切な変換がそれぞれ必要です。