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）及呼叫順序相同，就能重現相同序列。但只使用相同種子，不代表不同語言或 API 一定會產生相同結果。

從物理雜訊取得的熵，與以這些資訊作為種子、展開輸出序列的產生器，是不同層次。密碼學安全偽亂數產生器（CSPRNG）也包含決定性的處理，但透過合適的種子與設計，讓輸出難以預測。重點是MT19937 並非為密碼學用途而設計，而不是所有決定性程序都不能用於密碼學。

Intel 的 RDRAND 指令回傳的也不是未經處理的物理雜訊，而是決定性亂數位元產生器（DRBG）的輸出。不能把作業系統或 CPU 提供的亂數 API，一概稱為直接輸出原始「真亂數」。

週期是序列開始重複前的長度，不代表短種子可以選到所有初始狀態，也不是相鄰輸出互相獨立的證明。PHP 的 Mt19937 等採用 32 位元種子的 API，即使週期極長，可選擇的序列仍受到種子空間限制。

MT19937 的 623 維等分布性質是以 32 位元精度而言。把連續 623 個完整的 32 位元輸出組成一組，讓起點遍歷整個週期，每種位元組合出現的次數相同；唯一例外是全零組合會少出現一次。這個例外就是原論文定義的一部分。

若只保留 v 位元精度，就必須另外考慮對應的等分布維度 k(v)。位元精度與維度是不同概念，不能混用。

這項性質不保證短樣本內每個結果出現的次數相等，也不保證通過所有統計檢定，更不代表具有密碼學上的不可預測性。它也不同於 Fisher–Yates 洗牌每一步所需的條件式均勻選擇。

狀態更新會將相鄰字組的最高 1 位元與最低 31 位元接合，再使用右移、條件式 XOR，以及相隔 397 個字組的值。tempering 則對輸出字組套用位移與遮罩 XOR。這是可逆的位元轉換，不是加密。

以下教學範例採用2002 年版的單一 32 位元種子初始化方式，整數運算以 2³² 為模數。在 JavaScript 中，Math.imul 取得乘積的低 32 位元，>>> 則明確執行無號右移。twist 會依序覆寫同一個陣列；索引繞回後，也會讀取已更新的字組。若改成完全從舊陣列計算另一個新陣列，就會產生不同序列。

function mt19937(seed) {
  if (!Number.isInteger(seed) || seed < 0 || seed > 0xffffffff) {
    throw new RangeError("種子必須是 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 位元無號整數。這是教學實作，不是密碼學安全產生器，也不保證與所有語言的種子規則相容。

要重現結果，必須記錄產生器種類、函式庫及版本、初始化方式、種子或儲存的狀態、呼叫順序，以及轉換成指定範圍或分布的方法。產生一個整數、一個浮點數或一個常態分布值，不一定消耗相同數量的內部輸出。

不要預期本例的種子 5489 會與 Python 的 random.seed(5489) 產生相同序列，因為初始化方式不同。在平行處理中，給每個工作程序相同種子，也不會得到互相獨立的序列。應確認所用函式庫對亂數串流分割或衍生子串流（spawn）的規範。

若直接用 32 位元輸出除以 n 的餘數來對應整數範圍，當 2³² 無法被 n 整除時，就會出現偏差。選用 MT 並不能消除這種偏差；範圍轉換與產生器品質必須分開驗證。

廣泛採用不等於在每種用途下都是最佳選擇。也不能只憑過去的說明，就斷定目前所有 Excel 版本或未公開的內部實作都使用同一方式。

MT19937 不具密碼學安全性。狀態更新具有線性結構，tempering 又可逆，因此只要得知狀態，就能計算後續輸出。例如，若取得與狀態更新區塊邊界對齊的連續 624 個完整 32 位元輸出，就可以反轉 tempering 來重建狀態。

這並不是「觀察任何 624 次結果都一定能破解」的無條件主張。限定範圍的整數、由多個字組組合的浮點數、漏掉的輸出，以及其他呼叫穿插造成的狀態變化，都會改變觀測條件。但也不能把這些轉換當成 MT 安全性的依據。

密碼、機密權杖與金鑰，應使用適合用途的密碼學 API，例如瀏覽器的 crypto.getRandomValues()、Node.js 的 crypto.randomBytes()、Python 的 secrets 或 PHP 的 random_bytes()。nonce 需要唯一性還是不可預測性，應依協定要求判斷，不能認為 MT 會自動滿足兩者。

Web Crypto 要求產生具密碼學安全性的亂數，但沒有指定內部必須採用哪一種產生器。若取得亂數失敗時，悄悄改用 Math.random()，就會破壞機密值所需的安全條件。

SFMT 是針對 SIMD 設計的 MT 系列產生器；PCG 與 xoshiro 系列則有不同的設計取捨。不能把它們當成同一條後繼路線，直接排出高下。

比較時應統一目標 CPU、編譯器、整數位元數、分布轉換、平行亂數串流、統計檢定、可重現性及密碼學需求。沒有前提的「快 2.5 倍」或「品質世界第一」沒有可比較的意義。換成更快的非密碼學 PRNG，也不會因此獲得密碼學安全性。

以下整理目前 NanToo 日文版工具的亂數來源與使用方式。

這些是實作方式的說明。僅採用 Web Crypto API，並不保證與實體抽籤完全相同、已通過第三方公平性稽核，或符合抽獎、賭博等活動的法律要求。

ECMAScript 的 Math.random() 採用何種具體演算法，由實作決定；Web Crypto 也沒有指定 MT。上表介紹的是目前 NanToo 日文版工具，並不表示這些工具採用了本文的教學用 MT 程式碼。

產生器負責建立數值序列；Fisher–Yates 使用選出的數值來重新排列清單。機率計算又是另一件事：它在骰子獨立、均勻等理想化假設下，計算數學分布。骰子總和、擲四顆骰子後去掉最低一顆等理論分布，都不是 MT 特有的輸出保證。

基本原則是依用途選擇。可重現的實驗需要能記錄設定的 PRNG；機密值需要適當的 CSPRNG；無偏差的範圍對應則需要正確的轉換方法。