Cải tiến thuật toán cổ đại tìm số nguyên tố

Ngày nay, các nhà toán học vẫn luôn bị thôi thúc tìm ra các số nguyên tố mới và họ cũng nhận được rất nhiều tài chính và ưu ái để làm công việc này. Ngay từ thời Hy Lạp cổ đại, Eratosthenes, một nhà toán học, thiên văn học, đồng thời là người quản lý thư viện Alexandria, đã tìm ra một phương pháp phát hiện các số nguyên tố, được gọi là sàng Eratosthenes. Thuật toán chạy trên máy tính sử dụng nguyên lý của sàng Eratosthenes hoạt động rất tốn bộ nhớ. Nhà toán học Harald Helfgott (GS tại Đại học Göttingen, Đức) đã tìm ra cách sắp xếp các số trên sàng Eratosthenes để làm giảm bộ nhớ cần sử dụng. Kỹ thuật mới của ông giúp làm giảm bộ nhớ cần dùng đi rất đáng kể.

Nhà toán học Jean Carlos (Đại học Cornell, Mỹ) so sánh một cách dễ hình dung về khả năng tiết kiệm bộ nhớ này như sau: “Nếu chúng ta coi việc sử dụng bộ nhớ máy tính như việc sử dụng giấy, với thuật toán cũ để tìm các số nguyên tố từ 1 tới 1. 000.000 ta cần 10.000 tờ giấy thì với thuật toán mới này, ta chỉ cần sử dụng khoảng 100 tờ.”

Trước khi có thuật toán cải tiến này, chúng ta có rất nhiều thuật toán khác giúp tìm ra các số nguyên tố, phục vụ cho cơ sở mật mã hiện đại. Kỹ thuật của Harald Helfgott đã được trình bày tại Hội thảo chuyên đề về Đại số khu vực Mỹ Latin lần thứ XXI ở Buenos Aires; và Sinapsis 2016, sự kiện gặp gỡ của các nhà khoa học Peru sinh sống ở châu Âu, được tổ chức ở Paris.

Đức Hưng (theo Tia Sáng)