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) 會產生相同序列，因為兩者的初始化方法不同。在平行處理中，向每個工作程序（worker）提供相同種子，也不會得到互相獨立的序列。應先確認所用程式庫對隨機數串流分割或衍生子串流（spawn）的規定。

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

廣泛採用不代表在每種用途下都是最佳選擇。亦不能單憑過往的說明，就斷定現時所有 Excel 版本或未公開的內部實作都使用同一方法。

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

這並非「觀察任何 624 次結果都必定能破解」的無條件說法。限定範圍的整數、由多個字組組成的浮點數、遺漏輸出，以及其他呼叫穿插造成的狀態變化，都會改變觀測條件。但同樣不能把這些轉換當成 MT 具備安全性的理由。

密碼、機密權杖（token）和密鑰，應使用適合用途的密碼學 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；無偏差的範圍對應則需要正確的轉換方法。