Người tạo ra câu đố từng nói rằng phải mất gần 35 năm mới có thể tính toán ra được câu trả lời.

Vào đầu tháng 4/1999, một “viên nang thời gian” đã được chuyển đến cho kiến trúc sư nổi tiếng Frank Gehry với chỉ dẫn nhằm tích hợp nó vào các bản thiết kế của ông cho một toàn nhà mà sau này trở thành nơi “đóng đô” của Phòng thí nghiệm Khoa học máy tính và trí tuệ nhân tạo của MIT (viết tắt là CSAIL). “Viên nang thời gian” này về cơ bản là một viện bảo tàng về lịch sử sơ khai của máy tính, có chứa 50 món kỷ vật đóng góp bởi những người như Bill Gates và Tim Berners-Lee.

“Viên nang thời gian” không thể được mở ra trong vòng 35 năm tiếp theo – trừ khi có ai đó bẻ khóa được câu đố mã hóa kèm bên trong thiết kế của nó. Câu đố này được thiết kế bởi Ron Rivest, người được lấy tên đặt cho chữ “R” trong RSA – một trong những giao thức mã hóa quan trọng bậc nhất từng được tạo ra. Ông nói rằng câu đố không phức tạp. Thay vào đó, Rivest tạo ra câu đố và ước lượng rằng phải mất gần chính xác 35 năm để tính toán ra câu trả lời.

Vào ngày 15/4 vừa qua, gần 20 năm sau khi Rivest công bố câu đó, Bernard Fabrot, một lập trình viên tự học người Bỉ, đã giải được! Chỉ dẫn ban đầu của câu đố nói rằng lời giải phải được gửi đến giám đốc Phòng thí nghiệm Khoa học máy tính, nhưng Fabrot cho biết anh ngạc nhiên khi biết rằng phòng thí nghiệm đó không còn tồn tại nữa (nó đã được nhập vào phòng thí nghiệm AI của MIT vào năm 2003 để tạo ra CSAIL). Fabrot nói rằng giám đốc CSAIL là Daniela Rus thậm chí còn không biết đến sự tồn tại của câu đố khi anh này nói với bà về lời giải.

Câu đố của Rivest về cơ bản xoay quanh việc tìm ra con số thu được từ việc thực hiện phép tính bình phương gần 80 nghìn tỷ lần. Ví dụ, nếu bạn bắt đầu bằng việc tính bình phương của 2, bạn sẽ được 4, sau đó bình phương của 4 để được 16, và lặp lại quá trình này 80 nghìn tỷ lần nữa. Sau đó bạn lấy kết quả thu được và chạy một phương trình toán học sử dụng con số đó và một con số được cho trước trong hướng dẫn giải đố. Phương trình này sẽ cho ra một con số mới có thể được phiên dịch ra thành một cụm từ mang ý nghĩa chúc mừng (Rivest và Fabrot từ chối tiết lộ cụm từ này chính xác là gì, và họ sẽ công bố nó khi mở “viên nang thời gian” vào ngày 15/5 tới).

Mấu chốt của câu đố này là nó đòi hỏi phải thực hiện một chuỗi các phép tính liên tục, có nghĩa là bạn không thể tìm ra câu trả lời nhanh hơn bằng cách sử dụng điện toán song song được. Bạn cần thực hiện quá trình tính bình phương một cách tuần tự, tức phép tính trước phải có kết quả mới tiếp tục thực hiện phép tính tiếp theo – chính vì vậy, sử dụng thêm nhiều máy tính, hoặc giao công việc giải mã này cho một siêu máy tính, cũng không giải quyết được vấn đề gì. Dựa trên định luật Moore và quãng thời gian cần để chạy phép tính bình phương vào năm 1999, Rivest ước tính rằng tính toán ra được câu trả lời cho câu đó phải mất xấp xỉ 35 năm.
Ron Rivest

Ron Rivest

Fabrot, hiện là một nhà phát triển độc lập, cho biết anh vô tình gặp câu đố này vào năm 2015. Dù Rivest ban đầu tung ra mã của câu đó bằng ngôn ngữ Java, Fabrot nhận ra rằng nó có thể được giải nhanh hơn nếu dùng đến GNU Multiple Precision Arithmetic Library, một phần mềm miễn phí viết bằng ngôn ngữ C chuyên dùng vào việc thực hiện các phép tính số học chính xác. Vậy nên Fabrot đã dành riêng một trong số nhiều nhân CPU trên máy tính để bàn của mình để chạy phép tính bình phương nhằm giải câu đó. Anh cho biết máy tính của mình chạy phép tính 24/7, trừ những khi anh đi du lịch hoặc bị mất điện.

“Trong suốt nhiều năm, tôi không nói với ai về việc đang cố giải câu đố, trừ những người bạn rất thân. Tôi biết tôi có cơ hội, nhưng nếu tôi nói cho mọi người, họ có thể dùng một CPU mạnh mẽ hơn để vượt mặt tôi” – Fabrot nói.

Ba năm rưỡi sau, Fabrot cuối cùng cũng hoàn tất hơn 80 nghìn tỷ phép tính bình phương và thu được lời giải cho câu đó. Dù Fabrot không biết, nhưng có một nhóm các nhà khoa học máy tính và chuyên gia mã hóa cũng đang thực hiện một dự án có tên là Cryptophage, trong đó sử dụng phần cứng chuyên dụng được thiết kế dành riêng cho việc giải mã câu đố MIT đó.

Dẫn đầu bởi cựu kỹ sư Intel, Simon Peffers, nhóm Cryptophage lúc này đang nghiên cứu các chức năng trì hoãn có thể kiểm chứng để làm cơ chế bảo mật cho các blockchain như Ethereum. Các chức năng trì hoãn có thể kiểm chứng là một dạng hiện đại hơn của phương thức mã hóa trì hoãn thời gian sơ khai của Rivest, và lời giải của chúng chỉ có thể thu được thông qua các phép tính tuần tự nhau. Trong quá trình nghiên cứu, Peffers cho biết nhóm đã gặp câu đố của Rivest và nhận định rằng đây có vẻ là một ví dụ tốt cho việc thử nghiệm nghiên cứu của họ.

Vào giữa tháng 3, nhóm này bắt đầu chạy một thuật toán thiết kế bởi Erdinc Ozturk, một nhà nghiên cứu tại Đại học Sabanci, được tối ưu để giảm khoảng trì hoãn giữa các phép tính bình phương. Thuật toán này được triển khai trên một “mảng cổng lập trình được dạng trường” (FPGA), một con chip đa chức năng được lập trình để chạy một thuật toán cụ thể duy nhất, khiến nó hiệu quả hơn một CPU đại trà thông thường. Sử dụng thuật toán của Ozturk, FPGA này chạy nhanh gấp 10 lần so với một CPU thương mại cao cấp chạy phần mềm chưa được tối ưu hóa.

Nhờ vào khả năng tính toán hiệu quả của con chip, nhóm Cryptophage tính được rằng họ sẽ có lời giải chính xác cho câu đố của MIT vào tối ngày 10/5, chỉ 2 tháng sau khi bắt đầu quá trình tính toán. Thế nhưng khi họ liên hệ với MIT để thông báo rằng sắp có kết quả, Rivest thông báo cho họ biết Fabrot đã đi trước một bước!

“Chẳng có ai liên hệ với chúng tôi cho đến khi hai người đó xuất hiện vào cùng một ngày để thông báo rằng ‘chúng tôi đã giải được vấn đề của ông rồi'” – Rivest nói – “Quả là một sự trùng hợp đáng kinh ngạc”.

Rivest nhanh chóng thừa nhận rằng ông đã đánh giá quá cao độ khó của câu đố mình đặt ra. Đưa ra dự đoán về những cải tiến trong lĩnh vực công nghệ là điều rất khó nếu xét trên cả một quãng thời gian dài như vậy, và Rivest cho biết ông không ngờ đến những đột phá công nghệ, như chip FPGA – một thứ vào thời đó chưa phức tạp và phổ biến rộng rãi như ngày nay.

Dù nhóm Cryptophage không phải là người đầu tiên giải được câu đố, Peffers cho biết họ vẫn sẽ đến dự buổi lễ mở “viên nang thời gian” vào ngày 15/5 tới. Chỉ những người thiết kế ra “viên nang” biết được toàn bộ nội dung của nó, dù rằng nó chứa trong đó những đóng góp từ Tim Berners-Lee, nhà phát minh ra World Wide Web; Bob Metcalfe, người phát minh ra ethernet; và Bill Gates, người đã đóng góp phiên bản nguyên thủy của Altair BASIC, sản phẩm đầu tiên của Microsoft. Fabrot cho biết anh rất hào hứng để được thấy một bản sao nguyên bản của một trong những trò chơi PC đầu tiên, Zork, vốn được lưu trữ trong “viên nang”.

(theo Wired)

Tổ Chức Giáo Dục FPT – fpt.edu.vn

Trường Đào Tạo Lập Trình Viên Quốc Tế – aptech.fpt.edu.vn