Để 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
13:00 | 17/06/2024
Để tăng cường tính bảo mật và khắc phục các lỗ hổng, Microsoft thường phát hành định kỳ những bản cập nhật dành cho Windows, trong đó có các bản vá Patch Tuesday hàng tháng. Việc nắm bắt các bản vá này rất quan trọng để chủ động phòng tránh trước các mối đe dọa mạng. Bài viết này đưa ra quy trình cập nhật bản vá bảo mật Windows trên các máy trạm dành cho người dùng cuối, việc thực hiện cập nhật trên máy chủ Windows Server thực hiện tương tự.
14:00 | 01/03/2024
Giấu tin (steganography) là một kỹ thuật nhúng thông tin vào một nguồn đa phương tiện nào đó, ví dụ như tệp âm thanh, tệp hình ảnh,... Việc này giúp thông tin được giấu trở nên khó phát hiện và gây ra nhiều thách thức trong lĩnh vực bảo mật và an toàn thông tin, đặc biệt là quá trình điều tra số. Thời gian gần đây, số lượng các cuộc tấn công mạng có sử dụng kỹ thuật giấu tin đang tăng lên, tin tặc lợi dụng việc giấu các câu lệnh vào trong bức ảnh và khi xâm nhập được vào máy tính nạn nhân, các câu lệnh chứa mã độc sẽ được trích xuất từ ảnh và thực thi. Nhằm mục đích cung cấp cái nhìn tổng quan về phương thức ẩn giấu mã độc nguy hiểm, bài báo sẽ giới thiệu về kỹ thuật giấu tin trong ảnh và phân tích một cuộc tấn công cụ thể để làm rõ về kỹ thuật này.
08:00 | 10/02/2024
Hệ thống mật mã RSA là một trong các hệ mật mã khóa công khai đang được sử dụng rất phổ biến trong hệ thống mạng máy tính hiện nay. Việc lựa chọn tham số an toàn cho hệ mật RSA là vấn đề rất quan trọng trong cài đặt ứng dụng hệ mật này. Bài báo này trình bày chi tiết về khuyến nghị độ dài các tham số sử dụng cho hệ thống mật mã RSA như thừa số modulo, số mũ bí mật, số mũ công khai và các thừa số nguyên tố trong một số tiêu chuẩn mật mã của châu Âu, Đức và Mỹ.
10:00 | 26/10/2023
Trong thời gian gần đây, các trường hợp lừa đảo qua mã QR ngày càng nở rộ với các hình thức tinh vi. Bên cạnh hình thức lừa đảo cũ là dán đè mã QR thanh toán tại các cửa hàng khiến tiền chuyển về tài khoản kẻ gian, vừa qua còn xuất hiện các hình thức lừa đảo mới.
14:00 | 11/09/2024|Công nghệ PKI
11:00 | 03/09/2024|GP ATM
08:00 | 26/08/2024|GP ATM
10:00 | 19/08/2024|Tin tức sản phẩm
Một ví dụ điển hình trong việc triển khai mô hình Zero Trust thành công là của Tập đoàn công nghệ Microsoft. Điều này minh chứng cho cách một tổ chức lớn có thể bảo vệ tài nguyên và người dùng bằng các phương pháp kiểm soát nghiêm ngặt, đảm bảo an ninh mạng toàn diện. Đây cũng là bài học kinh nghiệm cho các tổ chức trong quá trình triển khai mô hình bảo mật hiện đại này.
10:00 | 14/11/2024
Trong bối cảnh an ninh mạng ngày càng trở nên phức tạp và tinh vi, các tổ chức đang dần nhận ra rằng các phương pháp bảo mật truyền thống không còn đáp ứng được yêu cầu bảo vệ hệ thống của họ. Chính trong hoàn cảnh này, mô hình Zero Trust nổi lên như một giải pháp toàn diện, giúp bảo vệ hệ thống mạng khỏi các cuộc tấn công cả từ bên ngoài và bên trong. Tuy nhiên, việc triển khai Zero Trust không đơn giản, bài học kinh nghiệm nào để các tổ chức triển khai thành công mô hình bảo mật hiện đại này?
13:00 | 11/11/2024
