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()，

而必须改用：