Để 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
08:00 | 15/03/2024
Bảo mật công nghệ trí tuệ nhân tạo (AI) đặt ra nhiều thách thức và luôn thay đổi trong bối cảnh chuyển đổi số hiện nay. Khi công nghệ AI phát triển, rủi ro và bề mặt tấn công cùng các mối đe dọa mới ngày càng tăng cao. Điều này đặt ra yêu cầu đối với các nhà phát triển, tổ chức và doanh nghiệp phải có cách tiếp cận chủ động, thường xuyên đánh giá và cập nhật các biện pháp bảo mật.
09:00 | 06/12/2023
Các cuộc chiến tranh giành lãnh địa trên không gian mạng trong tương lai sẽ xuất hiện và gia tăng giữa các nhóm tội phạm mạng khi nhiều đối thủ tập trung vào cùng một mục tiêu. Vừa qua Fortinet đã công bố Báo cáo Dự báo về các mối đe dọa an ninh mạng năm 2024 từ đội ngũ nghiên cứu FortiGuard Labs đưa ra những tác động của AI tới mô hình chiến tranh mạng, đồng thời nhấn mạnh xu hướng các mối đe dọa mới nổi có thể định hình bối cảnh chuyển đổi số trong năm tới và những năm sau.
10:00 | 21/04/2023
Hiện nay, các ứng dụng sử dụng hệ thống Internet vạn vật (Internet of Things - IoT) phát triển nhanh về số lượng dẫn đến những nguy cơ tiềm ẩn về lộ lọt dữ liệu nhạy cảm. Trong bài báo này, nhóm tác giả đề xuất một phương pháp mã hóa phân vùng trên máy tính nhúng sử dụng dm-crypt và LUKS để bảo vệ dữ liệu cho ứng dụng camera, đồng thời tích hợp thêm thuật toán mật mã Kuznyechik trong chuẩn GOST R34.12-2015 trên máy tính nhúng Raspberry Pi. Trong phần I, bài báo đi tìm hiểu về các phương pháp mã hóa dữ liệu và trình bày về các giải pháp mã hóa dữ liệu lưu trữ, giới thiệu nguyên lý hoạt động và một số công cụ phần mềm hỗ trợ mã hóa dữ liệu cả về thương mại lẫn mã nguồn mở, tìm hiểu sâu hơn về giải pháp mã hóa phân vùng bằng dm-crypt và LUKS trên máy tính nhúng, cụ thể là Raspberry Pi.
13:00 | 06/12/2022
Cùng với sự gia tăng không ngừng của các mối đe dọa an ninh mạng, các tin tặc thay đổi, phát triển các chiến thuật và phương thức tấn công mới tinh vi hơn dường như xuất hiện liên tục. Trong khi đó, các chiến dịch tấn công nhắm vào cơ sở hạ tầng công nghệ thông tin của các tổ chức/doanh nghiệp (TC/DN) được các nhóm tin tặc thực hiện với tần suất nhiều hơn. Chính vì thế, việc xây dựng một chiến lược phòng thủ dựa trên bằng chứng được thực thi tốt là điều mà các TC/DN nên thực hiện để chủ động hơn trước các mối đe dọa trong bối cảnh các cuộc tấn công mạng đang trở nên khó lường và phức tạp.
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
Hiện nay, số lượng các cuộc tấn công mạng nhắm đến hệ điều hành Linux đang ngày càng gia tăng cả về số lượng lẫn mức độ tinh vi, đặc biệt là các sự cố liên quan đến việc lộ lọt mật khẩu. Thông thường, khi tạo tài khoản mới trên Linux, người dùng có thể sử dụng những mật khẩu tùy ý, kể cả những mật khẩu yếu, điều này có thể gây ra nhiều rủi ro bảo mật tiềm ẩn trong hệ thống mạng, các tác nhân đe dọa sẽ dễ dàng tấn công và xâm phạm tài khoản hơn. Do đó, cần phải thực thi các chính sách sử dụng mật khẩu đủ mạnh để bảo vệ tài khoản người dùng tránh bị tấn công. Trong bài viết này sẽ gửi đến độc giả hướng dẫn thiết lập cấu hình mật khẩu an toàn trên Linux với nền tảng Centos 7.
10:00 | 10/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
