Xorshift128+ & PRNG Là Gì?

1. PRNG — Pseudo-Random Number Generator

PRNG (Bộ sinh số ngẫu nhiên giả) là thuật toán tạo ra chuỗi số có vẻ ngẫu nhiên nhưng thực chất hoàn toàn xác định (deterministic). Cho cùng một seed (hạt giống), PRNG luôn sinh ra cùng một chuỗi số.

Tại sao gọi "giả"? — Vì máy tính là máy xác định (deterministic machine). Không có gì thật sự ngẫu nhiên trong CPU. Mọi bit đều có nguyên nhân. PRNG chỉ tạo ra chuỗi số trông ngẫu nhiên nhờ các phép biến đổi toán học.

Các tính chất quan trọng của PRNG:

Chu kỳ (Period): Sau bao nhiêu số thì chuỗi lặp lại. Xorshift128+ có chu kỳ 2¹²⁸ − 1 ≈ 3.4 × 10³⁸
Phân phối đều (Uniform Distribution): Mỗi giá trị xuất hiện với xác suất gần bằng nhau
Deterministic: Cùng seed → cùng chuỗi (hữu ích cho reproducible testing)
Tốc độ: PRNG rất nhanh — vài nanosecond mỗi số

2. Xorshift128+ — Thuật Toán

Xorshift128+ là PRNG do Sebastiano Vigna đề xuất (2014), cải tiến từ Xorshift của George Marsaglia (2003). Đây là PRNG mặc định trong V8 (Chrome/Node.js), SpiderMonkey (Firefox), và JavaScriptCore (Safari) cho Math.random().

Tên gọi: "Xor" (phép XOR) + "Shift" (dịch bit) + "128" (128-bit state) + "+" (có phép cộng ở output)

Thuật toán chỉ dùng 3 phép toán bitwise cơ bản:

2.1. Pseudocode

// State: hai số 64-bit (s0, s1) — tổng 128-bit
function xorshift128plus():
    x = s0
    y = s1
    s0 = y                   // swap
    x = x XOR (x << 23)     // shift left + XOR
    x = x XOR (x >> 17)     // shift right + XOR
    x = x XOR (y >> 26)     // mix với nửa kia
    s1 = x
    return (x + y)           // output = cộng hai nửa

2.2. Triển khai C

#include <stdint.h>

static uint64_t s[2]; // 128-bit state

uint64_t xorshift128plus(void) {
    uint64_t x = s[0];
    uint64_t const y = s[1];
    s[0] = y;
    x ^= x << 23;          // a
    s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
    return s[1] + y;
}

2.3. Triển khai JavaScript

// BigInt version (minh họa — JS engines dùng C++ nội bộ)
let s0 = 1n, s1 = 2n; // seed
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);
  // >> 12 lấy 52 bits mantissa → [0, 1) giống Math.random()
}

2.4. Triển khai Python (tham khảo)

MASK64 = (1 << 64) - 1

def xorshift128plus(state):
    """state = [s0, s1] — mutable list"""
    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

# Sử dụng
state = [12345, 67890]  # seed bất kỳ (khác 0)
for _ in range(10):
    print(xorshift128plus(state))

3. Tại Sao Chrome/Firefox/Safari Chọn Xorshift128+?

Trước 2015, V8 (Chrome) dùng thuật toán MWC (Multiply-with-Carry) kém chất lượng — fail nhiều bài kiểm tra thống kê. Từ 2016, cả 3 engine lớn chuyển sang Xorshift128+ vì:

Cực nhanh: Chỉ 6 phép toán — 3 XOR, 2 shift, 1 add
Chất lượng tốt: Pass hầu hết các bộ kiểm tra (BigCrush, PractRand)
State nhỏ: Chỉ 128-bit (16 bytes) — cache-friendly
Chu kỳ dài: 2¹²⁸ − 1 ≈ 3.4 × 10³⁸ — đủ cho mọi ứng dụng non-crypto

4. Các PRNG Nổi Tiếng Khác

So sánh Xorshift128+ với các PRNG phổ biến:

Mersenne Twister (MT19937): Chu kỳ 2¹⁹⁹³⁷ − 1, state 2.5KB, Python random module dùng. Chậm hơn Xorshift
PCG (Permuted Congruential Generator): Chu kỳ 2⁶⁴, chất lượng thống kê excellent, nhỏ gọn
SplitMix64: Dùng để tạo seed cho Xorshift128+, Java 8+ SplittableRandom
LCG (Linear Congruential Generator): Cổ điển nhất (1958), chu kỳ ngắn, chất lượng kém — C rand()

5. Giới Hạn — Khi Nào KHÔNG Dùng PRNG

⚠️ PRNG (bao gồm Xorshift128+) KHÔNG AN TOÀN cho:

Mật mã (Cryptography): Dễ bị reverse-engineer — biết 4 output liên tiếp có thể khôi phục toàn bộ state
Token/session ID: Kẻ tấn công có thể dự đoán token tiếp theo
Lottery/gambling: Người chơi có thể đoán kết quả

Cho các trường hợp trên, phải dùng CSPRNG (xem bài tiếp theo).

6. Demo: Dự Đoán Math.random()

Chứng minh Xorshift128+ không an toàn: Nếu kẻ tấn công quan sát được vài output từ Math.random(), họ có thể khôi phục state và dự đoán mọi giá trị tiếp theo.

// Đây là lý do tại sao KHÔNG BAO GIỜ dùng Math.random() cho:
// - Tạo token
// - Tạo mật khẩu
// - Xáo bài poker

// ❌ KHÔNG AN TOÀN
const token = Math.random().toString(36).slice(2);

// ✅ AN TOÀN — dùng CSPRNG
const array = new Uint8Array(32);
crypto.getRandomValues(array);
const token = Array.from(array, b => b.toString(16).padStart(2, "0")).join("");

Xorshift128+ & PRNG Là Gì — Thuật Toán Sinh Số Ngẫu Nhiên Giả