Bài toán đếm mỗi lần một vẻ, nhưng gần như đều quy về hai câu hỏi: thứ tự có quan trọng không, và một phần tử có được chọn lại không? Bài này trả lời cả hai bằng ví dụ đời thường, mỗi ví dụ được tính chính xác bằng máy tính tổ hợp và số học, rồi chuyển sang nửa còn lại của công cụ: số nguyên tố, và vì sao tách một số thành các thừa số nguyên tố có thể khó hơn rất nhiều so với tạo ra nó.
Bốn công thức
| Mỗi phần tử tối đa một lần | Được lặp lại | |
|---|---|---|
| Có thứ tự | Chỉnh hợp: nPr = n! / (n − r)! | n^r |
| Không thứ tự | Tổ hợp: nCr = n! / (r! (n − r)!) | C(n + r − 1, r) |
Giai thừa n! = 1 × 2 × … × n đếm số cách xếp n vật khác nhau thành một hàng. Mọi công thức còn lại là giai thừa đã bỏ bớt những cách xếp không được tính riêng.
Bốn ví dụ đời thường
Bục trao giải. Tám vận động viên, vàng, bạc, đồng. Thứ tự quan trọng và không ai nhận hai huy chương: 8P3 = 8 × 7 × 6 = 336.
Pizza. Chọn 3 loại topping khác nhau trong 10. Thứ tự không quan trọng: C(10, 3) = 10 × 9 × 8 ÷ 3! = 720 ÷ 6 = 120. Nếu được chọn một loại hai lần ("gấp đôi phô mai"), đó là tổ hợp có lặp: C(10 + 3 − 1, 3) = C(12, 3) = 220.
Mã số. Mã 4 ký tự từ 26 chữ cái, được lặp, có thứ tự: 26⁴ = 456.976. Mã PIN 4 chữ số: 10⁴ = 10.000. Vì vậy mã PIN 4 số dựa vào việc giới hạn số lần thử, không phải vào số khả năng.
Xổ số. Vé Mega 6/45 chọn 6 số khác nhau trong 45 và thứ tự quay không quan trọng: C(45, 6) = 8.145.060. Trò 6/55: C(55, 6) = 28.989.675. Mọi bộ số đều có cùng khả năng, kể cả 1-2-3-4-5-6.
Một cách kiểm tra: nPr = nCr × r!. 120 bộ topping, mỗi bộ xếp theo 3! = 6 thứ tự, cho 720 = 10P3.
Các con số này tăng nhanh thế nào
Giai thừa vượt mọi thứ quen thuộc. 21! = 51.090.942.171.709.440.000 đã vượt giới hạn số nguyên 64 bit, và 52!, số cách xáo một bộ bài, có 68 chữ số: một bộ bài được xáo kỹ gần như chắc chắn đang ở một thứ tự chưa bộ bài nào từng có. Công cụ làm việc với số nguyên chính xác dài tùy ý, nên hiện được cả 35.660 chữ số của 10.000! trong khi máy tính thông thường báo tràn số hoặc làm tròn thành "2,846 × 10³⁵⁶⁵⁹".
Số nguyên tố: nhân thì dễ, tách thì khó
Giờ đi theo chiều ngược lại. Lấy hai số nguyên tố 1.000.000.007 và 1.000.000.009. Nhân chúng chỉ mất chốc lát: 1.000.000.016.000.000.063. Đi ngược lại, tìm hai số nguyên tố từ tích, là bài toán phân tích thừa số.
Cách đơn giản nhất, chia thử, thử mọi ước có thể tới căn bậc hai. Với tích 19 chữ số này là khoảng một tỷ ứng viên. Công cụ dùng Pollard rho, một bước đi ngẫu nhiên khéo léo tìm thừa số nguyên tố p trong khoảng √p bước: ở đây chừng 30.000 bước, nên kết quả hiện ra ngay.
Giờ tăng quy mô. Khối lượng công việc tăng theo kích thước của thừa số nguyên tố nhỏ nhất:
| Thừa số nguyên tố nhỏ nhất | Số bước ước tính của Pollard rho (√p) |
|---|---|
| 10 chữ số | 100.000 |
| 20 chữ số | 10.000.000.000 |
| 40 chữ số | 10²⁰ |
| 300 chữ số | 10¹⁵⁰ |
Với hai số nguyên tố 20 chữ số, công cụ hết hai giây cho phép và hiện phần chưa phân tích trong ngoặc. Các thuật toán chuyên dụng làm tốt hơn rho rất nhiều (sàng trường số tổng quát giữ kỷ lục; RSA-250, một số 829 bit gồm 250 chữ số, được phân tích năm 2020 sau hàng nghìn năm-lõi tính toán), nhưng mọi phương pháp đã biết trên máy tính thông thường vẫn mất thời gian không thực tế với số từ 600 chữ số trở lên.
Trực giác về RSA
Mã hóa RSA dựa đúng vào sự bất đối xứng này. Một người chọn hai số nguyên tố ngẫu nhiên lớn p và q, công bố tích n = p × q và giữ bí mật p, q. Mã hóa chỉ cần n và một số mũ công khai, bằng lũy thừa modulo: c = mᵉ mod n. Giải mã cần số mũ bí mật d, là nghịch đảo modulo của e theo (p − 1)(q − 1), và muốn tính (p − 1)(q − 1) phải biết p, q. Ai phân tích được n thì tính được d.
Bạn có thể thử các thành phần này ở thẻ ƯCLN và đồng dư: 4¹³ mod 497 = 445 là một phép "mã hóa" đồ chơi, còn 3⁻¹ mod 11 = 4 là một nghịch đảo đồ chơi, tìm bằng thuật toán Euclid mở rộng. Khóa thật dùng đúng các phép tính đó trên số dài hàng trăm chữ số. Việc chọn số nguyên tố cần kiểm tra tính nguyên tố nhanh: Miller–Rabin trong công cụ được chứng minh chính xác dưới 3,3 × 10²⁴, và lớn hơn thì kiểm tra Baillie–PSW chưa có phản ví dụ nào.
Đây là trực giác, không phải công thức thực hành: RSA thật còn cần đệm (padding), sinh khóa cẩn thận và mã chạy thời gian không đổi. Đừng tự viết mã hóa cho dữ liệu thật.
Những lỗi thường gặp
- Dùng chỉnh hợp khi thứ tự không quan trọng. Chọn ban cán sự 3 người trong 10 là C(10, 3) = 120, không phải 10P3 = 720.
- Quên việc được lặp. Chọn các viên kem mà vị có thể trùng là tổ hợp có lặp, không phải tổ hợp thường.
- Trộn công thức khi tính xác suất. Dùng một mô hình cho cả bài: nếu kết quả là tổ hợp thì số trường hợp thuận lợi cũng đếm bằng tổ hợp.
- Tin số thực dấu phẩy động với số đếm lớn. Hàm COMBIN của bảng tính làm tròn âm thầm với n lớn; số nguyên chính xác thì không.
- Hiểu "có thể là số nguyên tố" thành "thực tế có thể là hợp số". Với Baillie–PSW chưa từng tìm thấy phản ví dụ; dù vậy đó không phải chứng minh.
- Kết luận một số là nguyên tố vì không phân tích được. Hết thời gian chỉ có nghĩa là "chưa phân tích kịp", không phải "nguyên tố": kiểm tra nguyên tố mới là thứ quyết định.
Để xử lý kết quả thí nghiệm thay vì đếm chúng, máy tính thống kê tính trung bình, độ phân tán và xác suất nhị thức.