Phân tích một số ra thừa số nguyên tố là viết nó thành tích các số nguyên tố, ví dụ 1001 = 7 × 11 × 13. Với số nhỏ thì chỉ cần thử chia lần lượt, nhưng với số có vài trăm chữ số thì đến nay chưa ai biết cách làm nhanh: nhân hai số nguyên tố lớn mất một phần nghìn giây, còn tách ngược tích ấy có thể tốn hàng nghìn năm máy tính. Chính sự chênh lệch "nhân thì dễ, chia ngược thì khó" này là nền móng của mã hoá khoá công khai RSA, thứ bảo vệ phần lớn kết nối an toàn trên Internet.
Số nguyên tố và định lý cơ bản của số học
Số nguyên tố là số lớn hơn 1 chỉ chia hết cho 1 và chính nó: 2, 3, 5, 7, 11, 13… Số lớn hơn 1 không nguyên tố gọi là hợp số, và luôn tách được thành tích các số nguyên tố. Điều quan trọng hơn: cách tách là duy nhất, không kể thứ tự. 360 chỉ có một cách viết là 2³ × 3² × 5, dù bạn bắt đầu chia cho 2, cho 3 hay cho 5 trước.
Kết quả này gọi là định lý cơ bản của số học. Bộ Cơ sở của Euclid (khoảng năm 300 trước Công nguyên) đã có những mệnh đề then chốt dẫn tới nó, nhưng chứng minh đầy đủ và rõ ràng phần "duy nhất" thường được ghi cho Gauss trong cuốn Disquisitiones Arithmeticae năm 1801. Có thể coi số nguyên tố như những "nguyên tử" của số học: mọi số đều được ghép từ chúng theo một công thức riêng.
Cách phân tích bằng tay: chia thử
Cách đơn giản nhất là chia lần lượt cho các số nguyên tố 2, 3, 5, 7, 11… Mẹo quan trọng: chỉ cần thử đến căn bậc hai của số đó. Nếu n = a × b và cả a, b đều lớn hơn căn n thì tích phải lớn hơn n, vô lý. Vậy hợp số luôn có một ước không vượt quá căn bậc hai của nó.
Ví dụ phân tích 1001. Căn bậc hai của 1001 xấp xỉ 31,6, nên chỉ cần thử các số nguyên tố đến 31:
- 1001 lẻ, không chia hết cho 2.
- Tổng chữ số 1 + 0 + 0 + 1 = 2, không chia hết cho 3.
- Không tận cùng 0 hay 5, không chia hết cho 5.
- 1001 : 7 = 143. Chia hết.
- Tiếp tục với 143: thử 7 không được, thử 11 được 13.
- 13 là số nguyên tố.
Kết quả: 1001 = 7 × 11 × 13. (Đây cũng là lý do mẹo "viết một số ba chữ số hai lần" như 274274 luôn chia hết cho 7, 11 và 13: 274274 = 274 × 1001.)
Muốn biết các số nguyên tố để thử, người ta dùng sàng Eratosthenes, đặt theo tên nhà bác học Hy Lạp thế kỷ 3 trước Công nguyên: viết các số từ 2 đến 100, gạch bội của 2, rồi bội của 3, của 5, của 7. Những số còn lại là 25 số nguyên tố nhỏ hơn 100.
Mẹo Fermat cho số có hai thừa số gần nhau
Pierre de Fermat nghĩ ra một cách khác: tìm cách viết n thành hiệu hai bình phương, vì a² − b² = (a − b)(a + b). Ví dụ 8051: số chính phương gần nhất phía trên là 90² = 8100, hiệu 8100 − 8051 = 49 = 7². Vậy 8051 = 90² − 7² = 83 × 97. Một phép thử thay cho hàng chục lần chia. Mẹo này cực nhanh khi hai thừa số gần nhau, nên người tạo khoá mã hoá phải tránh chọn hai số nguyên tố quá sát nhau.
Vì sao số lớn lại khó đến thế
Chia thử với một số 20 chữ số cần thử đến khoảng 10 mũ 10, tức mười tỉ số: máy tính thường làm trong vài giây. Nhưng mỗi khi số chữ số tăng gấp đôi, khối lượng tăng theo cấp số nhân. Với số 600 chữ số, căn bậc hai có 300 chữ số; dù mỗi nguyên tử trong vũ trụ là một máy tính thử một tỉ phép chia mỗi giây từ thuở Big Bang, cũng chưa thử hết được.
Các nhà toán học đã có những thuật toán thông minh hơn chia thử rất nhiều, mạnh nhất hiện nay là sàng trường số tổng quát (general number field sieve). Nhưng ngay cả nó cũng chậm dần theo một tốc độ chỉ hơi chậm hơn cấp số nhân. Chưa ai chứng minh được không tồn tại cách nhanh, cũng chưa ai tìm ra. Đây là một trong những câu hỏi mở lớn của toán học và tin học.
| Mốc | Số được phân tích | Ghi chú |
|---|---|---|
| 1977 | RSA-129 (129 chữ số) được công bố làm thử thách | Đăng trên chuyên mục của Martin Gardner, tạp chí Scientific American |
| 1994 | RSA-129 bị phân tích | Khoảng 600 tình nguyện viên góp máy qua Internet; thông điệp giải ra là "The Magic Words are Squeamish Ossifrage" |
| 2009 | RSA-768 (232 chữ số) | Một nhóm quốc tế mất khoảng hai năm |
| 2020 | RSA-250 (250 chữ số, 829 bit) | Khoảng 2.700 năm-lõi máy tính, kỷ lục công khai tính tới thời điểm đó |
Trong khi đó, khoá RSA thông dụng hiện nay dài 2.048 bit, tương đương khoảng 617 chữ số thập phân, xa hơn kỷ lục rất nhiều.
Kiểm tra nguyên tố dễ, tìm thừa số khó
Một điều nghe ngược đời: biết một số có phải nguyên tố hay không lại dễ, kể cả với số hàng trăm chữ số. Các phép thử dựa trên định lý nhỏ Fermat trả lời trong tích tắc với xác suất sai nhỏ không đáng kể. Năm 2002, ba nhà toán học Ấn Độ Agrawal, Kayal và Saxena còn công bố thuật toán AKS, chứng minh được rằng việc kiểm tra nguyên tố có thể làm chắc chắn trong thời gian đa thức.
Nhưng các phép thử này chỉ nói "đây là hợp số", không chỉ ra thừa số là gì. Giống như biết chắc một ổ khoá có chìa mà không biết chìa nào. Nhờ khoảng cách này, ta tạo khoá mã hoá được dễ dàng (tìm hai số nguyên tố lớn ngẫu nhiên), còn kẻ muốn bẻ khoá thì bế tắc.
RSA thu nhỏ: mã hoá bằng phép chia lấy dư
RSA được Ron Rivest, Adi Shamir và Leonard Adleman công bố năm 1977. Về sau người ta biết nhà toán học Clifford Cocks ở cơ quan tình báo tín hiệu Anh đã tìm ra ý tưởng tương tự từ năm 1973, nhưng công trình được giữ bí mật đến năm 1997. Dưới đây là RSA với số tí hon, tính tay được:
- Chọn hai số nguyên tố: p = 5, q = 11. Tích n = 55 là phần công khai.
- Tính (p − 1)(q − 1) = 4 × 10 = 40. Con số này phải giữ bí mật, và chỉ tính được khi biết p, q.
- Chọn số mũ công khai e = 3 (không có ước chung với 40).
- Tìm số mũ bí mật d sao cho 3 × d chia 40 dư 1. Thuật toán Euclid mở rộng cho d = 27, vì 3 × 27 = 81 = 2 × 40 + 1.
- Mã hoá tin nhắn m = 8: tính 8³ = 512, chia 55 dư 17. Bản mã là 17.
- Giải mã: tính 17 mũ 27 chia 55 lấy dư, kết quả đúng bằng 8.
Ai cũng biết n = 55 và e = 3 để mã hoá gửi cho bạn, nhưng muốn tìm d thì phải biết 40, tức phải tách 55 thành 5 × 11. Với 55 thì trẻ lớp 6 cũng tách được. Với n dài 617 chữ số, đến nay không ai làm được. Toàn bộ bí mật nằm trong một bài toán chia.
Ngoài RSA, mật mã hiện đại còn dùng đường cong elliptic, dựa trên một bài toán khó khác, cho khoá ngắn hơn với cùng độ an toàn.
Góc nhìn hôm nay: máy tính lượng tử và mật mã mới
Năm 1994, Peter Shor chứng minh rằng một máy tính lượng tử đủ lớn sẽ phân tích được số lớn nhanh, đe doạ RSA. Các máy lượng tử hiện có còn quá nhỏ và quá nhiều nhiễu để làm điều đó với khoá thật, nhưng giới mật mã không chờ. Tháng 8/2024, Viện Tiêu chuẩn và Công nghệ Quốc gia Mỹ (NIST) công bố bộ tiêu chuẩn mật mã hậu lượng tử đầu tiên, dựa trên những bài toán toán học khác mà máy lượng tử cũng chưa biết cách giải nhanh. Các trình duyệt và ứng dụng nhắn tin lớn đã bắt đầu kết hợp mật mã mới với mật mã cũ.
Với người đọc phổ thông, bài học thực tế rất gọn: biểu tượng ổ khoá trên trình duyệt có ý nghĩa thật, nó dựa trên toán học đã được thử thách hàng chục năm; còn mật khẩu yếu thì không phép chia nào cứu được. Ai muốn đọc thêm về lịch sử mật mã có thể tìm cuốn The Code Book của Simon Singh, có chương riêng kể chuyện RSA và Clifford Cocks.
Câu hỏi thường gặp
Phân tích ra thừa số nguyên tố là gì?
Là viết một số thành tích các số nguyên tố, ví dụ 360 = 2³ × 3² × 5 hay 1001 = 7 × 11 × 13. Theo định lý cơ bản của số học, mỗi số lớn hơn 1 chỉ có đúng một cách phân tích như vậy, không kể thứ tự.
Cách phân tích một số ra thừa số nguyên tố nhanh?
Chia lần lượt cho các số nguyên tố 2, 3, 5, 7, 11… và chỉ cần thử đến căn bậc hai của số đó. Mỗi lần chia hết thì tiếp tục với thương. Nếu nghi hai thừa số gần nhau, thử viết số đó thành hiệu hai bình phương theo cách của Fermat.
Vì sao phân tích số lớn ra thừa số lại khó?
Vì khối lượng tính toán tăng gần như cấp số nhân theo số chữ số. Thuật toán tốt nhất hiện nay vẫn cần hàng nghìn năm-lõi máy tính cho số 250 chữ số, trong khi khoá RSA thông dụng dài khoảng 617 chữ số.
RSA liên quan gì đến số nguyên tố?
RSA tạo khoá bằng cách nhân hai số nguyên tố lớn bí mật. Tích được công khai để mã hoá, nhưng muốn tính khoá giải mã phải biết hai thừa số. Vì tách tích ấy quá khó, khoá giải mã được an toàn.
Máy tính lượng tử có phá được RSA không?
Về lý thuyết có: thuật toán Shor (1994) cho phép máy lượng tử đủ lớn phân tích số lớn nhanh. Các máy hiện có còn quá nhỏ để làm điều đó với khoá thật, và từ năm 2024 đã có tiêu chuẩn mật mã hậu lượng tử để thay thế dần.