Thuật toán Shor

Thuật toán Shor là một thuật toán lượng tử giúp phân tích nhân tử một số nguyên ở dạng "N" = "p"."q", với "p" và "q" là các số nguyên tố, tức là tìm ra các giá trị "p" và "q" khi cho số "N". Người ta sử dụng thuật toán này trên các máy tính lượng tử để phá mã RSA.
Lịch sử.
Thuật toán RSA là thuật toán mã hóa công khai được bắt nguồn bởi Ron Rivest, Adi Shamir và Leonard Adleman tại Học viện Công nghệ Massachusetts (MIT) vào năm 1977. Thuật mã hóa này dựa trên một sự thật rằng: để tìm phân tích nhân tử một số "N" (N=p.q với p,q là hai số nguyên tố) thành tích 2 số nguyên tố thì khó khăn hơn rất nhiều lần tính ra tích "N" của hai số nguyên tố p,q. Với tính toán cổ điển, hàm N(p,q) = pq là một hàm một chiều tức là việc tính ra N từ p và q có độ phức tạp nhỏ, O(0), còn việc tính ra p và q từ N có độ phức tạp cao. Ngay cả những siêu máy tính hiện đại mạnh mẽ nhất cũng sẽ cần nhiều thời gian hơn cả tuổi của vũ trụ nếu phân tích nhân tử một số 400 chữ số. Tính chất này được áp dụng cho việc xây dựng và ứng dụng mã hóa RSA.
Nếu có phương án phân tích nhân tử một số nguyên N nhanh thành p và q thì mã hóa RSA sẽ không còn an toàn trước các cuộc tấn công bẻ khóa. Thuật toán Shor đã thực hiện được việc phân tích nhân tử một số nguyên N thành p và q nhanh hơn các thuật toán cổ điển: chỉ trong thời gian đa thức. Ta có thể cần tới ) cổng lượng tử sử dụng phép nhân nhanh chóng khi tính toán và việc này hoàn toàn có thể giải quyết hiệu quả bằng máy tính lượng tử. Như vậy, nếu có một máy tính lượng tử có đủ số lượng qubit có thể hoạt động mà không bị ảnh hưởng bởi nhiễu lượng tử và các hiện tượng phục hồi tách sóng lượng tử khác, thuật toán Shor có thể được sử dụng để phá khóa RSA. Đây là một động lực mạnh mẽ cho việc thiết kế và xây dựng các máy tính lượng tử và cho việc nghiên cứu các thuật toán máy tính lượng tử học. Nó cũng đã tạo điều kiện nghiên cứu về hệ thống mã hóa mới an toàn trước các máy tính lượng tử, được gọi chung là mật mã hậu lượng tử.
Thuật toán.
Vấn đề chúng ta đang cố gắng giải quyết là: cho trước một hợp số lẻ N, tìm một số nguyên d giữa 1 và N, là ước N. Chúng ta chỉ quan tâm đến giá trị N lẻ bởi vì nếu N chẵn thì hiển nhiên một ước nguyên tố của nó phải là 2. Hơn nữa, để thuật toán làm việc hiệu quả, ta cần N không phải lũy thừa của một số nguyên tố. Điều này có thể kiểm tra bằng cách kiểm tra xem formula_1 có phải là số nguyên hay không, với mọi formula_2.
Sau khi hai điều kiện trên thỏa mãn, ta đã có N là tích của hai số nguyên tố lẻ phân biệt. Theo định lý Thặng dư Trung Hoa, 1 có ít nhất 4 nghiệm phân biệt theo mod N, trong đó 1 và -1 là hai nghiệm tầm thường. Mục đích của thuật toán là tìm ra thành phần nghiệm b còn lại ("b""2" đồng dư với 1 theo mod N) từ đó dẫn đến phân tích nhân tử N bằng sàng bậc 2.
Nhưng ta có thể đơn giản việc tìm b bằng cách tìm một thành phần a (ta sẽ trình bày rõ hơn ở dưới). Các thuật toán lượng tử được dùng để lựa chọn ngẫu nhiên số a đó thay cho phải tìm kiếm tuần tự như các phương pháp tính toán cổ điển.
Thuật toán Shor có hai phần:
1. Sử dụng thuật toán Miller, đưa bài toán về bài toán tìm kiếm tuần tự.
2. Sử dụng thuật toán lượng tử để giải quyết bài toán tìm kiếm tuần tự đó.
Cụ thể, trong thuật toán Shor, thực hiện lại hầu hết các bước của thuật toán Miller bằng tính toán cổ điển (1), ngoại trừ một bước có độ phức tạp cao nhất (2).
Bước 1:
Thuật toán Miller cổ điển gồm các bước sau:
Bước 2:
Trong thuật toán Miller, bước có độ phức tạp cao nhất là bước tìm chu kỳ r của hàm f(x). Để tìm chu kỳ của một hàm số, có thể biến đổi Fourier hàm số này, khi đó kết quả biến đổi Fourier sẽ cực đại tại các giá trị k/r với k là các số nguyên. Biến đổi Fourier có thể thực hiện nhanh hơn trong tính toán lượng tử, như đã trình bày ở mục bên trên. Do đó bước này có thể được thực hiện bằng tính toán lượng tử như sau.
Cụ thể, hàm f(x) làm hàm tuần hoàn có thể nhận tối đa N giá trị, và có thể được biểu diễn bằng Q bit, với Q là số nguyên nhỏ nhất lớn hơn lôgarit cơ số 2 của N. Có thể thiết lập một hệ vật lý gồm hai thanh ghi cạnh nhau, mỗi thanh gồm Q qubit, và thực hiện:
i) Khởi tạo thanh ghi thứ nhất, còn thanh ghi thứ hai ở trạng thái nghỉ (trạng thái năng lượng thấp nhất, thường ứng với qubit |0&gt;). Trạng thái của hệ 2 thanh ghi sau bước này là:
formula_3
ii) Xây dựng hàm f(x) thành toán tử lượng tử để áp dụng và hệ 2 thanh ghi sau bước trên, và thu được trạng thái mới của hệ là
formula_4
iii) Áp dụng biến đổi Fourier vào hệ.
Với formula_5, 
Lấy y là một trong r số nguyên dương mod N sao cho y.r/Q là số nguyên, ta có:
formula_6
Điều này dẫn đến trạng thái cuối:
formula_7
Ta viết lại tổng trên dưới dạng:
formula_8
Đây là một sự chồng chập của nhiều hơn Q trạng thái rất nhiều nhưng ít hơn rất nhiều so với "Q""2", từ đó suy ra có ít hơn Q giá trị phân biệt z = f(x). Lấy:
formula_12 là một vecto đơn vị trong mặt phẳng phức (trong đó formula_13 là căn đơn vị và "r", "y" là các số nguyên dương), thì hệ số formula_14 trong trạng thái cuối là:
formula_15
iv) Thực hiện phép đo, để trạng thái của hệ hai thanh ghi sụp về một trong các trạng thái riêng. Thanh ghi thứ nhất sụp về trạng thái ứng với chuỗi nhị phân thể hiện giá trị s, trong đó xác suất để s là bội số của 1/r là cao.
formula_16
v) Thử lại, bằng tính toán cổ điển, xem nếu f(x) = f(x + 1/s) thì kết thúc
vi) Nếu không thì thử, bằng tính toán cổ điển, với các giá trị là 1/sk với các k nguyên khác nhau, nếu một trong các giá trị này thỏa mãn thì kết thúc.
vii) Nếu không thì lặp lại từ bước đầu tiên