Thực thi thuật toán Shor phân tích thừa số của số nguyên trên IBM quantum Lab

Bài viết "Thực thi thuật toán Shor phân tích thừa số của số nguyên trên IBM quantum Lab" trình bày về việc áp dụng thực thi thuật toán Shor dựa trên nền tảng công nghệ đã góp phần thúc đẩy sự phát triển lý thuyết về tính toán toán điện tử, đồng thời mở ra một tương lai tiềm năng cho các ứng dụng của tính toán toán lượng tử trong lĩnh vực mật mã khóa công khai, tối ưu hóa tìm kiếm và phân tích dữ liệu, cũng như nhiều thách thức mới. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Thực thi thuật toán Shor phân tích thừa số của số nguyên trên IBM quantum Lab Hội nghị Quốc gia lần thứ 26 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2023) Thực thi thuật toán Shor phân tích thừa số của số nguyên trên IBM quantum Lab Nguyễn Đức Công, Hoàng Mạnh Toàn, Nguyễn Đình Đồng Học viện kỹ thuật mật mã, 141 Chiến Thắng, Tân Triều, Thanh Trì, Hà Nội Email: congechipvn@gmail.com, manhtoan2100@gmail.com, dongbeng35@gmail.com Abstract— Thuật toán do Peter Shor đề xuất, được lượng tử để cải thiện hiệu quả tính toán [5]. Trước khiđặt theo tên của nhà toán học, là một thuật toán lượng tử phân tích về thuật toán Shor thám hệ mật RSA, chúngđể phân tích số nguyên N trong thời gian đa thức. Thuật ta cần trình bày về biến đổi Fourier lượng tử được dùngtoán này đặt ra thách thức lớn đối với sự an toàn của các trong thuật toán. Mục đích của phép biến đổi Fourierhệ thống an toàn giao dịch sử dụng mật mã khóa công trong điện toán cổ điển để chuyển đổi bài toán rấtkhai RSA, bởi thuật toán Shor cho phép chạy trên một phong phú, từ chuyển miền tín hiệu cần xử lý nhằm nénmáy tính lượng tử có số qubit phù hợp sẽ phân tích nhanh dữ liệu đến các giải thuật đánh giá độ phức tạp tínhsố nguyên modulo thành tích của các thừa số nguyên tố. toán. Trong tính toán lượng tử, phép biến đổi Fourier làTrong khi, độ an toàn của thuật toán RSA phụ thuộc vào sự triển khai của biến đổi Fourier rời rạc đối với các giáthời gian phân tích số nguyên công khai N bằng tích củahai số nguyên tố lớn, do đó cách thức chung để phá vỡ hệ trị biên độ của trạng thái lượng tử. Biến đổi Fouriermật RSA nằm ở biên tính toán: với các thuật toán cổ điển lượng tử QFT (quantum Fourier transform) đóng vaithì biên này trở nên rất tốn thời gian khi số modulo N trò quan trọng của nhiều thuật toán lượng tử, nhất làngày càng lớn, cụ thể hơn, hiện chưa có thuật toán cổ điển khi ước lượng pha trong thuật toán Shor. Biến đổinào để phân tích số nguyên lớn N trong thời gian O(n3(log Fourier lượng tử QFT theo các trạng thái cơ sở của đầuN)). Tuy nhiên, thuật toán của Shor có thể cho phép phântích số lớn N trong thời gian đa thức. Giống như các thuật vào j sang cơ sở mới k được thể hiện bằng ánhtoán lượng tử khác, thuật toán Shor mang tính xác suất: xạ:nó đưa ra câu trả lời đúng với xác suất cao và xác suất 1 N 1 2ijkthất bại có thể giảm xuống nhờ thủ tục gọi lại nằm trong j  e N kthuật toán. N k 0 Do đó, biến đổi QFT còn được gọi là toán tử đơn vị Keywords- RSA, Shor Algorithm, Quantum Fourier (unitary) trong hệ tính toán n-qubit [1].Transform, Quantumn Gates Thực hiện biến đổi QFT của số nguyên lớn N  2 , ký n I. GIỚI THIỆU hiệu là QFTN , để chuyển từ trạng thái lượng tử Năm 1978, thuật toán RSA được tác giả Ron x  x1...xn , ( x1 là bit có trọng số cao), sang trạngRivest, Adi Shamir và Leonard Adleman lần đầu tiênmô tả công khai về cách mã hóa và giải mã thông tin thái lượng tử y  y1... yn sẽ có dạng như sau:theo giải pháp mới [3]. Thuật toán này mô tả một quy 1 N 1 2ixy 2 ntrình mã hóa cho phép truyền thông tin một chiều với QFTN x  e yđộ bảo mật cao. Phương pháp mã hóa này được sử N y 0dụng rộng rãi trong nhiều dịch vụ ngày nay [5]. Do đó, Và khi biểu diễn giá trị trạng thái y dưới dạng phâncác hệ thống sử dụng thuật toán RSA này sẽ phản ứng số nhị phân:đáng báo động, nếu ai đó xuất hiện và tuyên bố rằng họ yk yk 1 y1 ncó cách bẻ khóa mã hóa. Không cố tỏ ra quá kịch tính, y   2  ...  k   yk 2ksong đó thực chất là những gì mà Peter Shor đã làm khi 21 2 2 k 1đưa ...