Xorshift128+ 與 PRNG 是什麼？偽隨機數產生演算法完整介紹

1. 什麼是 PRNG（Pseudo-Random Number Generator）？

PRNG（偽隨機數產生器）

是一種利用演算法產生「看起來隨機」數列的方法。

它產生的數值並不是真正的隨機，

而是：

完全由演算法決定（Deterministic）。

只要使用相同的 Seed（種子），

就一定會得到完全相同的數列。

因此，

PRNG 十分適合：

模擬；
遊戲；
測試；
科學計算；
程式設計中的一般亂數需求。

為什麼稱為「偽」隨機？

因為電腦本身是一部：

確定性機器（Deterministic Machine）。

CPU 的每一個位元，

都有明確的計算來源。

真正完全不可預測的亂數，

並不存在於一般 CPU 運算之中。

PRNG

只是透過數學運算，

產生一串：

統計上近似隨機的數列。

PRNG 的主要特性

Deterministic：相同 Seed 一定得到相同結果
Uniform Distribution：各個值出現機率大致相同
Period（週期）：經過一定次數後數列開始重複
High Performance：速度極快，每次產生通常只需數奈秒

以 Xorshift128+ 為例，

其週期為：

2¹²⁸ − 1

約等於：

3.4 × 10³⁸

對一般用途而言幾乎不可能用盡。

2. Xorshift128+ 演算法

Xorshift128+

由 Sebastiano Vigna 於 2014 年提出，

是 George Marsaglia 所提出 Xorshift 系列的改良版本。

目前，

Chrome（V8）、

Firefox（SpiderMonkey）、

Safari（JavaScriptCore）

都曾採用或採用過這類演算法，

作為：

Math.random()

背後的 PRNG。

名稱由來

Xor：XOR 位元運算
Shift：位元位移
128：128-bit 內部狀態
+：輸出時加入加法混合

整個演算法，

幾乎只使用：

XOR
Left Shift
Right Shift
Addition

四種極快的 CPU 指令。

3. 演算法流程

內部狀態包含：

兩個 64-bit 整數。

總共：

128 bit。

流程如下：

x = s0
y = s1

s0 = y

x ^= x << 23
x ^= x >> 17
x ^= y >> 26

s1 = x

return x + y

雖然只有少量位元運算，

卻能產生品質相當高的偽隨機數列。

4. C 語言實作

#include <stdint.h>

static uint64_t s[2];

uint64_t xorshift128plus $void$  {
    uint64_t x = s[0];
    uint64_t const y = s[1];

    s[0] = y;

    x ^= x << 23;
    s[1] = x ^ y ^ (x >> 17) ^ (y >> 26);

    return s[1] + y;
}

5. JavaScript 範例

let s0 = 1n;
let s1 = 2n;

const MASK64 = (1n << 64n) - 1n;

function xorshift128plus() {
    let x = s0;
    const y = s1;

    s0 = y;

    x ^= (x << 23n) & MASK64;
    x ^= x >> 17n;
    x ^= y >> 26n;

    s1 = x;

    return Number(((x + y) & MASK64) >> 12n) / (2 ** 52);
}

此程式僅用於說明演算法。

實際瀏覽器中的

Math.random()

通常由 C++ 原生程式實作。

6. Python 範例

MASK64 = (1 << 64) - 1

def xorshift128plus $state$ :
    x = state[0]
    y = state[1]

    state[0] = y

    x ^= (x << 23) & MASK64
    x ^= x >> 17
    x ^= y >> 26

    state[1] = x

    return (x + y) & MASK64


state = [12345, 67890]

for _ in range(10):
    print $xorshift128plus(state)$

7. 為什麼瀏覽器採用 Xorshift128+？

在較早版本中，

Chrome 使用的是：

MWC（Multiply-with-Carry）。

其統計品質較差，

無法通過部分大型隨機測試。

之後，

主要 JavaScript Engine 改採：

Xorshift128+，

原因包括：

速度極快

僅需：

3 次 XOR
2 次 Shift
1 次 Addition

即可完成一次亂數生成。

統計品質優秀

能通過：

BigCrush
PractRand

等大型隨機測試。

狀態非常小

只需要：

128 bit

（16 Bytes）。

十分適合 CPU Cache。

週期極長

2¹²⁸ − 1

足以滿足幾乎所有：

非密碼學用途。

8. 常見 PRNG 比較

| 演算法 | 特點 | |---------|------| | Xorshift128+ | 極快、128-bit 狀態、統計品質佳 | | Mersenne Twister | 週期極長（2¹⁹⁹³⁷−1），Python random 使用 | | PCG | 狀態小，統計品質極佳 | | SplitMix64 | 常用於產生 Seed | | LCG | 最古老，品質較差，C rand() 曾廣泛使用 |

9. PRNG 不適合哪些用途？

雖然 PRNG 很快，

但：

不能用於安全用途。

包括：

密碼學；
Session ID；
API Token；
JWT Secret；
一次性驗證碼；
線上博彩；
抽獎系統。

原因是：

只要取得足夠輸出，

攻擊者便可能：

推算內部狀態，

預測之後所有亂數。

因此，

安全需求必須改用：

CSPRNG（Cryptographically Secure PRNG）。

10. 為什麼不能用 Math.random() 產生 Token？

例如：

const token = Math.random().toString(36).slice(2);

這種做法：

並不安全。

原因是：

Math.random()

通常建立在：

一般 PRNG，

而不是：

密碼學安全亂數。

正確方式應使用：

const bytes = new Uint8Array(32);

crypto.getRandomValues $bytes$ ;

const token = Array.from $bytes$ 
    .map $b =&gt; b.toString(16).padStart(2, &quot;0&quot;)$ 
    .join("");

其中：

crypto.getRandomValues()

使用的是：

瀏覽器提供的

CSPRNG，

適合：

Token
Session ID
Password
Key
Salt
Security Nonce

等安全用途。

結論

Xorshift128+

是一種經典且高效率的

偽隨機數產生演算法（PRNG）。

它具有：

極高速度；
很長的週期；
良好的統計品質；
很小的記憶體需求。

因此，

非常適合：

遊戲；
模擬；
科學計算；
一般程式中的亂數需求。

但它仍然屬於：

Deterministic PRNG。

對於任何涉及：

密碼學或安全性的場景，

都不能使用 Xorshift128+ 或 Math.random()，

而必須改用：