Để 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.
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.
10:00 | 13/12/2023
Meta đã chính thức triển khai hỗ trợ mã hóa đầu cuối - End-to-end encryption (E2EE) trong ứng dụng Messenger cho các cuộc gọi và tin nhắn cá nhân theo mặc định trong bản cập nhật mới lần này, bên cạnh một số bộ tính năng mới cho phép người dùng có thể kiểm soát và thao tác dễ dàng và hiệu quả hơn trong các cuộc trò chuyện.
10:00 | 20/09/2023
ChatGPT và các mô hình ngôn ngữ lớn (LLM) tương tự đã làm tăng thêm độ phức tạp trong bối cảnh mối đe dọa trực tuyến ngày càng gia tăng. Tội phạm mạng không còn cần các kỹ năng mã hóa nâng cao để thực hiện gian lận và các cuộc tấn công gây thiệt hại khác chống lại các doanh nghiệp và khách hàng trực tuyến nhờ vào bot dưới dạng dịch vụ, residential proxy, CAPTCHA và các công cụ dễ tiếp cận khác. Giờ đây, ChatGPT, OpenAI và các LLM khác không chỉ đặt ra các vấn đề đạo đức bằng cách đào tạo các mô hình của họ về dữ liệu thu thập trên Internet mà LLM còn đang tác động tiêu cực đến lưu lượng truy cập web của doanh nghiệp, điều này có thể gây tổn hại lớn đến doanh nghiệ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
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
