Ngày 9 tháng 9, Cognition công bố nhà nghiên cứu Eric Lu của công ty đã dùng tác nhân lập trình Devin do chính hãng phát triển để hoàn thành việc phân tích thừa số RSA-260 — kỷ lục công khai lớn nhất hiện nay trong thử thách phân tích thừa số RSA. Kỷ lục trước đó, RSA-250, dừng lại vào tháng 2 năm 2020, cách đây sáu năm rưỡi.
RSA-260 là một số thập phân 260 chữ số, được tách thành hai số nguyên tố 130 chữ số. Thuật toán sử dụng không mới — vẫn là sàng trường số tổng quát (GNFS), phương pháp chuẩn để phân tích số nguyên lớn từ những năm 1990. Thay đổi nằm ở tầng triển khai: toàn bộ quy trình được chuyển từ cụm CPU sang GPU.
4.900 GPU-ngày được dùng vào đâu
Cognition đưa ra phân bổ: chọn đa thức 643 GPU-ngày, sàng lưới 3.813 GPU-ngày, giải hệ phương trình tuyến tính 467 GPU-ngày. Bước sàng chiếm hơn ba phần tư tổng năng lực tính toán, đúng với đặc trưng thường thấy của GNFS.
Công cụ then chốt là một bộ sàng lưới GPU tên glas, viết lại bằng CUDA, kết hợp với bản CADO-NFS đã được cải biến và một phiên bản thuật toán khối Wiedemann tối ưu cho GPU. Cognition cho biết cách triển khai này giảm chi phí đơn vị của bước sàng khoảng một bậc độ lớn.
CADO-NFS chính là phần mềm mã nguồn mở mà đội Pháp dùng để phân tích RSA-250 năm 2020. Cùng một nền tảng mã, chỉ đổi phần cứng phía sau, khoảng cách sáu năm thể hiện qua hai con số này.
Việc Devin làm ở đây là công việc kỹ thuật, không phải phát hiện toán học: tối ưu mã, chỉnh tham số, quản lý cụm máy. Cognition mô tả nó trong bài viết là một "kỹ sư phần mềm đủ giỏi để giải quyết các bài toán ở giao điểm giữa lý thuyết số tính toán và kỹ thuật hiệu năng GPU".
Sự tham gia của con người cũng được ghi vào dữ liệu công khai: 233 phiên làm việc, 82.702 từ hướng dẫn. Tính trung bình mỗi phiên hơn 300 từ, gần bằng lượng ghi chú của một lần review code. Đây không phải là chạy không giám sát, mà là một người cùng một công cụ có thể làm việc liên tục, ép công việc vốn cần một đội phối hợp trong nhiều tháng xuống còn ba tuần.
Ngoại suy lên sẽ ra sao
Cognition tiện thể đưa ra hai ước tính ngoại suy, đều ghi chú là tính sơ bộ theo giá GPU hiện tại: độ khó của RSA-1024 khoảng gấp 78 lần RSA-260, chi phí khoảng 30 triệu USD; độ khó của RSA-2048 gấp 9,12 nghìn tỷ lần, chi phí được viết là 3,77×10^16 USD.
Con số đầu tiên đáng để dừng lại suy nghĩ. Mức 30 triệu USD là điều các tổ chức cấp quốc gia chi trả được, doanh nghiệp lớn cũng chi trả được. RSA-1024 từ lâu không còn được khuyến nghị trong các tiêu chuẩn, nhưng vẫn còn tồn tại trong thiết bị nhúng, chữ ký firmware phiên bản cũ, và một số chuỗi chứng thư không còn ai bảo trì. Khoảng cách chừng một tỷ lần giữa hai con số là toàn bộ lý do khiến 2048-bit hiện vẫn còn đứng vững.
Nhìn theo trục thời gian: năm 1999 RSA-155 bị phân tích với ước tính công khai khoảng 8.000 MIPS-năm; cuối năm 2009 RSA-768 quy đổi ra khoảng 2.000 năm trên một lõi Opteron 2,2GHz; năm 2020 RSA-250 là 2.700 lõi-năm; lần này là 13,5 GPU-năm. Ba lần trước, tiến bộ chủ yếu đến từ định luật Moore và tinh chỉnh thuật toán, nhịp độ đại khái mỗi thập kỷ một mốc. Bước nhảy lần này gộp cả việc đổi thế hệ phần cứng lẫn câu hỏi "ai là người viết đoạn mã CUDA đó" vào làm một.
Phần chưa có câu trả lời
Bài báo và mã nguồn có được công bố đầy đủ hay không, glas có mã nguồn mở hay không, thông báo của Cognition không đề cập. Bên thứ ba độc lập chưa tái hiện được phép tính này — RSA-250 khi đó từng được nhiều đội chéo kiểm chứng tham số sàng, còn kết quả lần này hiện chỉ có dữ liệu từ một phía.
Bản thân kết quả phân tích dễ kiểm chứng, chỉ cần nhân hai số nguyên tố lại. Khó kiểm chứng là khoản chi phí: 4.900 GPU-ngày dùng loại GPU nào, đơn giá bao nhiêu, có tính cả những lần thử thất bại hay không — thông báo không tách chi tiết từng khoản. Con số 400.000 USD có ý nghĩa gì với việc đánh giá an toàn, phụ thuộc vào những chi tiết đó.
Nguồn tham khảo: blog kỹ thuật chính thức của Cognition, thông báo phân tích RSA-250 trên caramba.loria.fr, CocoLoop; đơn vị GPU-ngày và lõi-năm được trích dẫn nguyên văn theo từng thông báo, không quy đổi thống nhất.