- Giới thiệu
- Số nguyên tố có thể giải thích dễ dàng nhưng lại chứa độ phức tạp khổng lồ
- Được sử dụng trong các lĩnh vực như khái niệm toán học, trực quan hóa thú vị, mật mã học và nhiều nơi khác
- Quyết định thử sức tạo số nguyên tố bằng lập trình
- Thử thách
- Tạo các số nguyên tố có thể dùng cho thuật toán RSA
- Vì độ dài khóa RSA hiện tại là 2048 bit, nên cần 2 số nguyên tố kích thước 1024 bit
- Ràng buộc:
- Viết mã từ đầu (không dùng phụ thuộc bên ngoài)
- Chỉ sử dụng CPU AMD Ryzen 7 và RAM 16GB của máy tính xách tay
- Tạo số nguyên tố trong thời gian "hợp lý"
- Chọn ngôn ngữ Rust
- Tạo số nguyên tố 16 bit
- Sinh số ngẫu nhiên bằng bộ tạo số giả ngẫu nhiên
/dev/urandom
- Dùng phương pháp thử chia (Trial Division), một kỹ thuật kiểm tra nguyên tố đơn giản
- Có thể tạo số nguyên tố 16 bit trong khoảng trung bình 40ms
- Tạo số nguyên tố 64 bit
- Cài đặt thuật toán thử chia đã được tối ưu hóa
- Chỉ kiểm tra các số có dạng 6k±1
- Tạo trước danh sách các số nguyên tố nhỏ để lọc trước các số dễ chia hết
- Sau khi tối ưu hóa mất khoảng 6 giây
- Với các số lớn hơn, thuật toán xác định thuần túy có giới hạn
- Kiểm tra nguyên tố xác suất
- Áp dụng Định lý nhỏ của Fermat (Fermat's Little Theorem)
- Có nhược điểm là hợp số cũng có thể thoả mãn điều kiện (Pseudoprimes)
- Kiểm tra nguyên tố Miller-Rabin (Miller-Rabin Primality Test)
- Phương pháp xác suất được cải tiến từ phép kiểm tra của Fermat
- Không có hợp số nào luôn trở thành Pseudoprime đối với một cơ số (base) nào đó
- Xác suất lỗi rất thấp nên có thể dùng trong thực tế
- Tạo số nguyên tố 128 bit
- Có thể tạo nhanh bằng kiểm tra Miller-Rabin (khoảng 0.03 giây trung bình)
- Khó mở rộng đến 1024 bit vì giới hạn của kiểu dữ liệu
u128
- Cài đặt BigInt cho 1024 bit
- Cải tiến dần qua nhiều lần thử
- Lần thử 1: Lưu từng chữ số của số vào mảng
- Lần thử 2: Lưu số dưới dạng nhị phân
- Lần thử 3: Lưu số theo từng khối byte
- Lần thử 4: Lưu số theo từng khối
u64
- Lần thử 5: Tối ưu hóa các thuật toán bốn phép tính cơ bản
- Tối ưu hóa kiểm tra Miller-Rabin và toàn bộ logic
- Tối ưu hóa song song bằng đa luồng (multithreading)
- Kết quả cuối cùng
- Có thể tạo số nguyên tố 1024 bit trong khoảng 40ms (8ms ~ 800ms)
- Nhờ xử lý song song, trung bình chỉ mất 0.04 giây
Ý kiến của GN⁺
- Quá trình lặp đi lặp lại thử thách và thất bại rồi cải tiến dần rất đáng chú ý
- Bắt đầu từ bản cài đặt đơn giản rồi áp dụng ý tưởng mới và tối ưu tại mỗi bước
- Dù gặp thất bại, vẫn không từ bỏ mà tìm nguyên nhân gốc rễ và giải pháp
- Dù kiến thức toán học của tác giả không nhiều, nỗ lực tra cứu tài liệu và cố gắng hiểu để áp dụng vẫn nổi bật
- Học các khái niệm toán cần thiết như Định lý nhỏ Fermat, kiểm tra Miller-Rabin
- Hiểu được cả nội dung khó đến mức có thể triển khai thực tế
- Việc tự xây dựng BigInt để vượt qua hạn chế của kiểu số nguyên có độ dài cố định là ấn tượng
- Không chỉ sử dụng thư viện sẵn có, mà còn hiểu cơ chế bên trong và tối ưu hóa
- Thử nhiều ý tưởng khác nhau và từng bước nâng cấp là điều dễ thấy
- Việc tối ưu hóa hiệu năng đáng kể nhờ xử lý song song bằng đa luồng rất đáng chú ý
- Nhận diện đúng tính chất của bài toán là các phép toán độc lập rồi tận dụng nó
- Không chỉ đơn thuần chạy nhanh hơn mà là cách tiếp cận hiệu quả dựa trên bản chất bài toán
- Mặc dù chưa đạt mức an toàn mật mã, vẫn là một dự án có ý nghĩa lớn về mặt học tập và khám phá
- Đây là bài toán nhấn mạnh tính tò mò và tinh thần thách thức của tác giả hơn là mục đích ứng dụng thực tế
- Những hiểu biết và kinh nghiệm thu được trong quá trình này được kỳ vọng sẽ giúp tác giả phát triển mạnh mẽ trong tương lai
1 bình luận
Ý kiến trên Hacker News
Liên quan đến điểm này, một số tiền điện tử sử dụng các thứ liên quan đến việc tìm số nguyên tố lớn như một phần của hàm proof of work. Khoảng 8 năm trước, có thể kiếm được khá nhiều tiền từ một triển khai kiểm tra nguyên tố siêu nhanh. Tác giả từng là người viết và quản lý phần mềm đào cho Riecoin trong một thời gian.
Bài viết này bỏ qua phép nhân Montgomery, tối ưu hóa hàng đầu cho kiểm tra nguyên tố nhanh. Đây là nền tảng cho việc triển khai phép mũ mô-đun (modular exponentiation) nhanh và thực dụng.
CGBN do Niall Emmart phát hành là thư viện bigint trên GPU cực nhanh. Đây vẫn là triển khai batch modexp nhanh nhất mà mình biết.
Python có một modexp tích hợp khá tốt:
pow(x, y, m)→x^y % m, nên có thể triển khai dễ dàng kiểm tra nguyên tố Fermat hoặc Miller-Rabin.Ban đầu, ý tưởng về kiểm tra nguyên tố xác suất có vẻ lạ nên mình cố gắng tìm thuật toán xác định cho các số cực lớn, nhưng APR-CL và ECPP quá phức tạp về mặt toán học để hiểu được. Sau đó nhận ra hầu như mọi nơi, kể cả RSA, đều dùng thuật toán xác suất.
Việc làm cho Miller-Rabin trở thành xác định trong một giới hạn tối đa của số là hiển nhiên. Chỉ cần chọn các cơ sở đã được chứng minh loại bỏ tất cả số giả nguyên tố trong giới hạn đã cho.
Nhân số lớn có thể được giản đơn hóa bằng một dòng assembly nội tuyến. Giá như thêm khái niệm nhân mở rộng vào ngôn ngữ C. Hỗ trợ phần cứng xuất hiện ở mọi nơi.
Phép thử Fermat đã đủ vì thuật toán sẽ không chạy nếu số đó không thực sự là số nguyên tố. Nhưng mình không biết liệu có thể chứng minh rằng không tồn tại các giá trị P/Q không phải nguyên tố vẫn cho phép mã hóa/giải mã thành công thông điệp hay không.
Mình tò mò dự án này mất bao lâu. Tác giả đã triển khai Karatsuba, Toom-Cook, FFT số phức, NTT, và Schönhage–Strassen. Anh ấy còn đề xuất sách của Silverman: 'A Friendly Introduction to Number Theory'.
Khi tự viết mã nhân số lớn, mình đồng cảm với việc việc chuyển lời giải thích cấp cao từ bài báo toán sang tính toán thực tế thật khó khăn. Có một chút lỗi trong phần giải thích về cơ số.
Tối ưu hóa cuối cùng: thêm 2 thay vì tạo số mới, làm giảm nhẹ tính an toàn. Vì số nguyên tố không phân bố đồng đều, nên sẽ bị lệch về phía số nguyên tố ngay sau khoảng cách nguyên tố lớn.
Có một chút lỗi trong phần giải thích về Định lý nhỏ của Fermat. Nó nói rằng a^(p-1) chia hết cho p, nhưng thực tế phải là a^(p-1) - 1 chia hết cho p. Nhưng theo thuật ngữ số học mô-đun thì phần này lại đúng.