{"slug":"xorshift128-plus-prng-la-gi-thuat-toan-so-ngau-nhien-gia","title":"Xorshift128+ & PRNG Là Gì — Thuật Toán Sinh Số Ngẫu Nhiên Giả","summary":"PRNG là gì? Phân tích chi tiết Xorshift128+ — thuật toán sinh số ngẫu nhiên giả mặc định trong Chrome/Firefox/Safari (Math.random()). Pseudocode, triển khai C/JS/Python, so sánh PRNG, giới hạn bảo mật.","excerpt":"PRNG là gì? Phân tích chi tiết Xorshift128+ — thuật toán sinh số ngẫu nhiên giả mặc định trong Chrome/Firefox/Safari (Math.random()). Pseudocode, triển khai C/JS/Python, so sánh PRNG, giới hạn bảo mật.","markdown":"# Xorshift128+ & PRNG Là Gì?\n## 1. PRNG — Pseudo-Random Number Generator\nPRNG (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ố.\n\n**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.\n\nCác tính chất quan trọng của PRNG:\n\nChu kỳ (Period): Sau bao nhiêu số thì chuỗi lặp lại. Xorshift128+ có chu kỳ 2¹²⁸ − 1 ≈ 3.4 × 10³⁸\nPhâ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\nDeterministic: Cùng seed → cùng chuỗi (hữu ích cho reproducible testing)\nTốc độ: PRNG rất nhanh — vài nanosecond mỗi số\n## 2. Xorshift128+ — Thuật Toán\nXorshift128+ 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().\n\n**Tên gọi: **\"Xor\" (phép XOR) + \"Shift\" (dịch bit) + \"128\" (128-bit state) + \"+\" (có phép cộng ở output)\n\nThuật toán chỉ dùng 3 phép toán bitwise cơ bản:\n\n### 2.1. Pseudocode\n// State: hai số 64-bit (s0, s1) — tổng 128-bit\nfunction xorshift128plus():\nx = s0\ny = s1\ns0 = y // swap\nx = x XOR (x << 23) // shift left + XOR\nx = x XOR (x >> 17) // shift right + XOR\nx = x XOR (y >> 26) // mix với nửa kia\ns1 = x\nreturn (x + y) // output = cộng hai nửa\n### 2.2. Triển khai C\n#include \n\nstatic uint64_t s[2]; // 128-bit state\n\nuint64_t xorshift128plus(void) {\nuint64_t x = s[0];\nuint64_t const y = s[1];\ns[0] = y;\nx ^= x << 23; // a\ns[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c\nreturn s[1] + y;\n}\n### 2.3. Triển khai JavaScript\n// BigInt version (minh họa — JS engines dùng C++ nội bộ)\nlet s0 = 1n, s1 = 2n; // seed\nconst MASK64 = (1n << 64n) - 1n;\n\nfunction xorshift128plus() {\nlet x = s0;\nconst y = s1;\ns0 = y;\nx ^= (x << 23n) & MASK64;\nx ^= x >> 17n;\nx ^= y >> 26n;\ns1 = x;\nreturn Number(((x + y) & MASK64) >> 12n) / (2 ** 52);\n// >> 12 lấy 52 bits mantissa → [0, 1) giống Math.random()\n}\n### 2.4. Triển khai Python (tham khảo)\nMASK64 = (1 << 64) - 1\n\ndef xorshift128plus(state):\n\"\"\"state = [s0, s1] — mutable list\"\"\"\nx = state[0]\ny = state[1]\nstate[0] = y\nx ^= (x << 23) & MASK64\nx ^= x >> 17\nx ^= y >> 26\nstate[1] = x\nreturn (x + y) & MASK64\n\n# Sử dụng\nstate = [12345, 67890] # seed bất kỳ (khác 0)\nfor _ in range(10):\nprint(xorshift128plus(state))\n## 3. Tại Sao Chrome/Firefox/Safari Chọn Xorshift128+?\nTrướ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ì:\n\nCực nhanh: Chỉ 6 phép toán — 3 XOR, 2 shift, 1 add\nChất lượng tốt: Pass hầu hết các bộ kiểm tra (BigCrush, PractRand)\nState nhỏ: Chỉ 128-bit (16 bytes) — cache-friendly\nChu kỳ dài: 2¹²⁸ − 1 ≈ 3.4 × 10³⁸ — đủ cho mọi ứng dụng non-crypto\n## 4. Các PRNG Nổi Tiếng Khác\nSo sánh Xorshift128+ với các PRNG phổ biến:\n\nMersenne Twister (MT19937): Chu kỳ 2¹⁹⁹³⁷ − 1, state 2.5KB, Python random module dùng. Chậm hơn Xorshift\nPCG (Permuted Congruential Generator): Chu kỳ 2⁶⁴, chất lượng thống kê excellent, nhỏ gọn\nSplitMix64: Dùng để tạo seed cho Xorshift128+, Java 8+ SplittableRandom\nLCG (Linear Congruential Generator): Cổ điển nhất (1958), chu kỳ ngắn, chất lượng kém — C rand()\n## 5. Giới Hạn — Khi Nào KHÔNG Dùng PRNG\n⚠️ PRNG (bao gồm Xorshift128+) KHÔNG AN TOÀN cho:\n\nMậ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\nToken/session ID: Kẻ tấn công có thể dự đoán token tiếp theo\nLottery/gambling: Người chơi có thể đoán kết quả\n\nCho các trường hợp trên, phải dùng CSPRNG (xem bài tiếp theo).\n\n## 6. Demo: Dự Đoán Math.random()\nChứ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.\n\n// Đây là lý do tại sao KHÔNG BAO GIỜ dùng Math.random() cho:\n// - Tạo token\n// - Tạo mật khẩu\n// - Xáo bài poker\n\n// ❌ KHÔNG AN TOÀN\nconst token = Math.random().toString(36).slice(2);\n\n// ✅ AN TOÀN — dùng CSPRNG\nconst array = new Uint8Array(32);\ncrypto.getRandomValues(array);\nconst token = Array.from(array, b => b.toString(16).padStart(2, \"0\")).join(\"\");","html":"

1. PRNG — Pseudo-Random Number Generator

\n

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ố.

\n

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.

\n

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

\n\n

2. Xorshift128+ — Thuật Toán

\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().

\n

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

\n

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

\n

2.1. Pseudocode

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

2.2. Triển khai C

\n
#include <stdint.h>\n\nstatic uint64_t s[2]; // 128-bit state\n\nuint64_t xorshift128plus(void) {\n    uint64_t x = s[0];\n    uint64_t const y = s[1];\n    s[0] = y;\n    x ^= x << 23;          // a\n    s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c\n    return s[1] + y;\n}
\n

2.3. Triển khai JavaScript

\n
// BigInt version (minh họa — JS engines dùng C++ nội bộ)\nlet s0 = 1n, s1 = 2n; // seed\nconst MASK64 = (1n << 64n) - 1n;\n\nfunction xorshift128plus() {\n  let x = s0;\n  const y = s1;\n  s0 = y;\n  x ^= (x << 23n) & MASK64;\n  x ^= x >> 17n;\n  x ^= y >> 26n;\n  s1 = x;\n  return Number(((x + y) & MASK64) >> 12n) / (2 ** 52);\n  // >> 12 lấy 52 bits mantissa → [0, 1) giống Math.random()\n}
\n

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

\n
MASK64 = (1 << 64) - 1\n\ndef xorshift128plus(state):\n    """state = [s0, s1] — mutable list"""\n    x = state[0]\n    y = state[1]\n    state[0] = y\n    x ^= (x << 23) & MASK64\n    x ^= x >> 17\n    x ^= y >> 26\n    state[1] = x\n    return (x + y) & MASK64\n\n# Sử dụng\nstate = [12345, 67890]  # seed bất kỳ (khác 0)\nfor _ in range(10):\n    print(xorshift128plus(state))
\n

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

\n

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ì:

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

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

\n

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

\n\n

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

\n

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

\n\n

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

\n

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

\n

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.

\n
// Đây là lý do tại sao KHÔNG BAO GIỜ dùng Math.random() cho:\n// - Tạo token\n// - Tạo mật khẩu\n// - Xáo bài poker\n\n// ❌ KHÔNG AN TOÀN\nconst token = Math.random().toString(36).slice(2);\n\n// ✅ AN TOÀN — dùng CSPRNG\nconst array = new Uint8Array(32);\ncrypto.getRandomValues(array);\nconst token = Array.from(array, b => b.toString(16).padStart(2, "0")).join("");
","tags":["Công nghệ","Lập trình","Thuật toán"],"author":"System Legacy","publishedAt":"2026-04-04T07:48:10.976Z","updatedAt":"2026-07-17T02:35:44.182Z","published_at":"2026-04-04T07:48:10.976Z","updated_at":"2026-07-17T02:35:44.182Z","view_count":175,"canonical":"https://wiki.quizzman.com/wiki/xorshift128-plus-prng-la-gi-thuat-toan-so-ngau-nhien-gia","url":"https://wiki.quizzman.com/wiki/xorshift128-plus-prng-la-gi-thuat-toan-so-ngau-nhien-gia","markdownUrl":"https://wiki.quizzman.com/api/articles/xorshift128-plus-prng-la-gi-thuat-toan-so-ngau-nhien-gia.md","apiUrl":"https://wiki.quizzman.com/api/articles/xorshift128-plus-prng-la-gi-thuat-toan-so-ngau-nhien-gia"}