Để nhân hai số lớn, chúng ta phải nhân từng chữ số của số thứ nhất với từng chữ số của só thứ hai. Khi nhân hai số mà mỗi số có N chữ số, chúng ta sẽ phải thực hiện N2 (hay N x N) phép nhân. Phương pháp này đã được sử dụng từ khoảng 4000 năm nay, từ thời của những người Babylon và Ai Cập cổ đại. Năm 1956, nhà toán học Liên Xô Kolmogorov phỏng đoán rằng đó là cách tốt nhất để nhân hai số. Ông cho rằng nếu có cách làm tốt hơn thì con người đã tìm ra nó. Nhưng chỉ vài năm sau, phỏng đoán của Kolmogorov đã được chứng minh là sai.
Năm 1960, Anatoly Karatsuba, một sinh viên toán 23 tuổi ở Nga, đã tìm ra thủ thuật đại số giúp giảm số phép nhân cần thực hiện. Để nhân hai số có 4 chữ số, thay vì phải thực hiện 4 x 4 = 16 phép nhân, chúng ta chỉ cần thực hiện 9 phép nhân khi sử dụng phương pháp của Karatsuba. Khi số chữ số càng lớn thì thời gian tiết kiệm được càng lớn. Với những số có hàng ngàn chữ số, Karatsuba giúp tốc độ nhân tăng tới 17 lần so với cách nhân thông thường.
Một trong những công việc cần tới phép nhân hai số lớn là mã hóa. Mỗi khi người dùng cần mã hóa thông tin trao đổi trên internet – khi truy cập dịch vụ ngân hàng điện tử hay tìm kiếm một thứ gì đó trên mạng – thiết bị của họ đều phải thực hiện những phép nhân với các số có hàng trăm hay hàng ngàn chữ số. Nhưng với những ứng dụng cần xử lý những số có hàng triệu hay hàng tỷ chữ số thì thuật toán của Karatsuba vẫn là quá chậm.
Một đột phá xuất hiện năm 1971, khi hai nhà toán học Đức là Arnold Schönhage và Volker Strassen đưa ra giải pháp sử dụng thuật toán biến đổi nhanh Fourier (FFT) để nhân các số lớn. FFT là một trong những thuật toán quan trọng nhất của thế kỷ 20. Một ứng dụng rất phổ biến của nó là âm nhạc số, mỗi khi người dùng nghe một tệp MP3, dùng dịch vụ nghe nhạc trực tuyến hay đài phát thanh số, đều có thuật toán FFT đứng đằng sau hậu trường để giải mã âm thanh.
Trong tài liệu công bố năm 1971, Schönhage và Strassen còn đưa ra một phỏng đoán quan trọng.
Nửa đầu của phỏng đoán là có thể nhân hai số có N chữ số bằng N x log (N) phép toán. Thuật toán của họ chưa thật sự đạt tới ngưỡng đó nhưng họ nghĩ rằng nó có thể được cải tiến. Trong các thập kỷ sau đó, một số nhà nghiên cứu đã tìm ra cách cải tiến thuật toán của Schönhage và Strassen. Đáng kể nhất là thuật toán năm 2007 của Martin Fürer (nhưng chính ông này cũng cho rằng việc tiếp tục cải tiến vượt quá khả năng của mình).
Nửa sau của phỏng đoán là phần chứng minh hơn rất nhiều: N x log (N) chính là giới hạn không thể vượt qua (hay không có thuật toán nhân số lớn nào có thể làm tốt hơn).
Vào giữa tháng 2/2019, Joris van der Hoeven (trường École Polytechnique, Pháp) và David Harvey (trường UNSW, Úc) đã công bố một tài liệu mô tả thuật toán nhân số lớn mới có thể đạt tới ngưỡng N x log (N), hoàn thành phần dễ của phỏng đoán Schönhage–Strassen. Thay vì dùng FFT một chiều – cách mà tất cả các công trình nghiên cứu về vấn đề này từ năm 1971 tới nay – thuật toán mới sử dụng FFT đa chiều. Cách làm này không phải mới xuất hiện: định dạng ảnh phổ biến JPEG dựa trên các phép FFT 2 chiều và FFT 3 chiều được sử dụng khá nhiều trong vật lý và kỹ thuật. Trong tài liệu mới công bố, hai nhà toán học đã sử dụng FFT với 1729 chiều – thứ có vẻ khá khó hình dung nhưng về mặt toán học thì không phức tạp hơn nhiều so với FFT 2 chiều.
Theo hai ông, việc nhân hai số với mỗi số có một tỷ chữ số bằng máy tính sẽ tốn hàng tháng. Nhưng với thuật toán Schönhage-Strassen, thời gian giảm xuống còn dưới 30 giây và với thuật toán mới được tìm ra thì thời gian còn giảm hơn nữa. Tuy nhiên, thuật toán mới chưa thể áp dụng trong thực tế vì cách chứng minh trong tài liệu mới chỉ đúng cho những số cực lớn. Theo tài liệu FAQ mà hai nhà toán học công bố, họ cũng không biết số lớn tới mức nào thì áp dụng được (tuy họ đưa ra một ví dụ khoảng 10214857091104455251940635045059417341952).
Hai nhà nghiên cứu hy vọng công trình nghiên cứu của họ sẽ được hoàn thiện tiếp và thuật toán sẽ có thể dùng cho những số với vài tỷ hay vài ngàn tỷ chữ số. Nếu điều này thành hiện thực thì thuật toán mới sẽ trở thành công cụ hữu ích cho công nghệ máy tính.
Công trình nghiên cứu mới này vẫn chưa được đánh giá, thẩm định bởi các nhà nghiên cứu trong ngành nhưng mọi người đều hy vọng nó sẽ được công nhận là đúng. Riêng về nửa sau của phỏng đoán, David Harvey và Joris van der Hoeven cùng mong rằng nó sẽ được chứng minh là sai (giống như phỏng đoán của Kolmogorov).
Nguyễn Anh Tuấn
09:00 | 17/09/2018
07:00 | 14/06/2019
15:00 | 10/07/2018
08:00 | 06/03/2020
13:00 | 09/05/2018
08:00 | 12/08/2019
15:00 | 14/08/2019
09:00 | 07/06/2023
Công ty an ninh mạng Kaspersky đã phát hành một công cụ rà quét mã độc mới để phát hiện IPhone cũng như các thiết bị iOS khác có bị nhiễm phần mềm độc hại “Triangulation” trong chiến dịch tấn công APT (Advanced Persistent Threat) gần đây hay không.
17:00 | 18/01/2023
Ngày nay, mạng không dây đang trở nên phổ biến trong các tổ chức, doanh nghiệp và cá nhân. Sự ra đời, phát triển và cải tiến không ngừng của mạng Wifi đã giải quyết được những hạn chế trước đó của mạng có dây truyền thống. Tuy nhiên, công nghệ mạng Wifi vẫn còn tồn tại những điểm yếu liên quan đến tính bảo mật và an toàn thông tin (ATTT). Do tính chất môi trường truyền dẫn vô tuyến nên mạng Wifi rất dễ bị rò rỉ thông tin do tác động của môi trường bên ngoài, đặc biệt là sự tấn công từ các tin tặc.
16:00 | 30/11/2022
Trong phần I của bài báo, nhóm tác giả sẽ giới thiệu cách thức xây dựng bộ dữ liệu IDS2021-WEB trích xuất từ bộ dữ liệu gốc CSE-CIC-IDS2018. Theo đó, các bước tiền xử lý dữ liệu được thực hiện từ bộ dữ liệu gốc như lọc các dữ liệu trùng, các dữ liệu dư thừa, dữ liệu không mang giá trị. Kết quả thu được là một bộ dữ liệu mới có kích thước nhỏ hơn và số lượng thuộc tính ít hơn. Đồng thời, đề xuất mô hình sử dụng bộ dữ liệu về xây dựng hệ thống phát hiện tấn công ứng dụng website.
09:00 | 25/11/2022
Kiểm thử xâm nhập là một giải pháp ngăn chặn các cuộc tấn công mạng hữu hiệu nhất. Nhưng không giống như các phương thức hay giải pháp bảo mật khác, kiểm thử xâm nhập chống lại mối đe dọa bằng cách tự suy nghĩ và hành động như một mối đe dọa để xâm nhập thử vào hệ thống hay ứng dụng của tổ chức. Kết quả kiểm tra sau đó được sử dụng để khắc phục các lỗi đang tồn tại trong hệ thống hoặc ứng dụng mà chưa được biết đến, bằng cách tinh chỉnh và tăng cường bảo mật.
08:00 | 11/01/2024 | Chính sách - Chiến lược
09:00 | 10/01/2024 | Giải pháp khác
09:00 | 05/01/2024|Chính sách - Chiến lược
09:00 | 05/01/2024|An ninh – Quốc Phòng
Những ngày gần đây, liên tục các kênh YouTube với lượng người theo dõi lớn như Mixigaming với 7,32 triệu người theo dõi của streamer nổi tiếng Phùng Thanh Độ (Độ Mixi) hay Quang Linh Vlogs - Cuộc sống ở Châu Phi với 3,83 triệu người theo dõi của YouTuber Quang Linh đã bị tin tặc tấn công và chiếm quyền kiểm soát.
10:00 | 22/04/2024
Mới đây, Cơ quan An ninh mạng và Cơ sở hạ tầng Hoa Kỳ (CISA) đã phát hành phiên bản mới của hệ thống Malware Next-Gen có khả năng tự động phân tích các tệp độc hại tiềm ẩn, địa chỉ URL đáng ngờ và truy tìm mối đe dọa an ninh mạng. Phiên bản mới này cho phép người dùng gửi các mẫu phần mềm độc hại để CISA phân tích.
13:00 | 17/04/2024
