Bài 16: Máy tính tạo số ngẫu nhiên thế nào? Từ xúc xắc trong game đến mã OTP

Máy tính là cỗ máy làm đúng từng bước được lập trình – vậy làm sao nó "tung xúc xắc", xáo bài trong game hay tạo mã OTP gửi về điện thoại? Câu trả lời thú vị: phần lớn số "ngẫu nhiên" trên máy tính thực ra hoàn toàn được tính toán trước.

Bài thứ mười sáu của chuyên mục "Thuật toán trong đời sống": số giả ngẫu nhiên và số ngẫu nhiên thật.

1. Số giả ngẫu nhiên

Theo Cloudflare, thuật toán tạo số trên máy tính được gọi là "giả ngẫu nhiên" vì kết quả không thực sự ngẫu nhiên: cùng đầu vào sẽ luôn cho cùng đầu ra. Đầu vào đó gọi là hạt giống (seed).

2. Bộ sinh đồng dư tuyến tính (LCG)

Một trong những cách đơn giản và lâu đời nhất:

X_n+1 = (a · X_n + c) mod m
Ví dụ nhỏ (giáo trình của GS Karl Sigman, ĐH Columbia): a = 5, c = 1, m = 8, X₀ = 0 cho dãy 0, 1, 6, 7, 4, 5, 2, 3 rồi lặp lại.

Dãy nhìn có vẻ lộn xộn nhưng thực chất là một vòng lặp. Với m lớn (như 2³² hay 2⁶⁴) và hệ số chọn khéo, vòng lặp đủ dài để dùng cho game hay mô phỏng đơn giản.

3. Mersenne Twister – "ngôi sao" của mô phỏng

Năm 1998, Makoto Matsumoto và Takuji Nishimura (Nhật Bản) công bố Mersenne Twister. Theo trang của tác giả, chu kỳ của nó được chứng minh là 2¹⁹⁹³⁷ − 1 – một số có hơn 6000 chữ số. Ngày nay:

• Module random của Python dùng Mersenne Twister làm bộ sinh lõi.
• C++ có sẵn std::mt19937 từ chuẩn C++11 – học sinh thi đấu dùng nó để sinh test và cho các thuật toán ngẫu nhiên.

LCG, Mersenne Twister và module secrets

#include <bits/stdc++.h>
using namespace std;
// Bộ sinh đồng dư tuyến tính (LCG): x = (a*x + c) mod m
struct LCG {
    uint64_t x;
    LCG(uint64_t seed) : x(seed) {}
    uint32_t next(){ x = (6364136223846793005ULL * x + 1442695040888963407ULL); return x >> 33; }
};
int main(){
    LCG g(2026);                       // cùng hạt giống -> cùng dãy số
    cout << "LCG seed 2026: ";
    for(int i = 0; i < 5; i++) cout << g.next() % 100 << ' ';
    cout << "\n";
    mt19937 mt(2026);                  // Mersenne Twister trong thư viện chuẩn C++
    uniform_int_distribution<int> dice(1, 6);
    int cnt[7] = {};
    for(int i = 0; i < 600000; i++) cnt[dice(mt)]++;
    for(int f = 1; f <= 6; f++) cout << "Mat " << f << ": " << cnt[f] << "\n";
}

import random, secrets

class LCG:
    def __init__(self, seed):
        self.x = seed
    def next(self):
        # x = (a*x + c) mod 2^64, lấy 31 bit cao
        self.x = (6364136223846793005 * self.x + 1442695040888963407) % 2**64
        return self.x >> 33

g = LCG(2026)
print("LCG seed 2026:", [g.next() % 100 for _ in range(5)])

random.seed(2026)                     # Python dùng Mersenne Twister
counts = [0] * 7
for _ in range(600000):
    counts[random.randint(1, 6)] += 1
print("Do xuc xac 600000 lan:", counts[1:])

# Số ngẫu nhiên cho mục đích bảo mật (mật khẩu, mã OTP): dùng module secrets
print("Ma OTP:", f"{secrets.randbelow(10**6):06d}")

Kết quả chạy:

LCG seed 2026: 87 36 53 63 68
Mat 1: 100574
Mat 2: 99501
Mat 3: 100127
Mat 4: 99632
Mat 5: 100142
Mat 6: 100024

Chạy lại bao nhiêu lần với seed 2026, bạn cũng nhận được đúng dãy số đó – rất tiện để tái hiện lỗi khi kiểm thử chương trình. 600.000 lần tung, mỗi mặt xuất hiện khoảng 100.000 lần: phân bố đều như mong muốn.

4. Khi "giả" là không đủ: bảo mật

Tài liệu Python ghi rõ: vì hoàn toàn tất định, các bộ sinh trong module random không phù hợp cho mục đích bảo mật; với mật khẩu, mã OTP, khóa mã hóa hãy dùng module secrets. Tác giả Mersenne Twister cũng cho biết thuật toán này dành cho mô phỏng Monte-Carlo, không an toàn mật mã. Nếu kẻ gian quan sát đủ nhiều số liên tiếp, họ có thể đoán được các số tiếp theo.

5. Ngẫu nhiên thật từ thế giới vật lý

• Bức tường đèn dung nham: tại văn phòng San Francisco, Cloudflare đặt khoảng 100 chiếc đèn dung nham. Camera chụp chúng; mỗi bức ảnh là một con số rất lớn, được đưa vào bộ sinh số an toàn mật mã.
• RANDOM.ORG lấy độ ngẫu nhiên từ nhiễu khí quyển.
• Xổ số tự động: theo Thông tư 36/2019/TT-BTC của Bộ Tài chính, quay số mở thưởng có thể dùng lồng cầu hoặc hệ thống điện tử hoàn toàn tự động, kết quả phải được tạo hoàn toàn ngẫu nhiên và có quay thử trước để phát hiện bất thường.

6. Bạn học được gì từ đây?

• Phép mod lại xuất hiện – lần này để tạo ra sự "hỗn loạn" có kiểm soát.
• Chọn đúng công cụ: mt19937/random cho mô phỏng và sinh test; secrets cho bảo mật.
• Trong thi đấu, thuật toán ngẫu nhiên (xáo trộn, chọn chốt ngẫu nhiên, hash ngẫu nhiên) giúp tránh bị test "bẫy".

Bài tập luyện tập

• CSES – Josephus Problem I
• Dùng mt19937 viết chương trình sinh test ngẫu nhiên cho một bài bạn đã giải, rồi so sánh với lời giải trâu – kỹ thuật "đối chiếu" (stress test) mà mọi học sinh thi đấu nên biết.
• Ước lượng số π bằng phương pháp Monte-Carlo: gieo điểm ngẫu nhiên trong hình vuông, đếm số điểm rơi vào hình tròn nội tiếp.

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 17: Xếp hàng ở siêu thị có thể tính trước? Lý thuyết hàng đợi

Đọc tiếp: lý thuyết hàng đợi →

← Bài trước: nhận diện khuôn mặtXem tất cả 27 bài →

Nguồn tham khảo

• Cloudflare – Lava lamp encryption
• Cloudflare Blog (06/11/2017) – Randomness 101: LavaRand in production
• Matsumoto – What is Mersenne Twister?
• Python docs – random
• cppreference – std::mersenne_twister_engine
• Karl Sigman, Columbia University – Linear congruential generators
• RANDOM.ORG
• LuatVietnam – Quy trình quay số mở thưởng (Thông tư 36/2019/TT-BTC)