✨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 $\backslash sqrt[k]\{N\}$ có phải là số nguyên hay không, với mọi $k\; \backslash le\; \backslash log\_\{2\}(N)$.

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² đồ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:

• Chọn một số ngẫu nhiên a < N.
• Tìm ƯCLN(a, N), có thể dùng thuật toán Ơclit cho bước này.
• Nếu ƯCLN(a, N) ≠ 1, thì p = ƯCLN(a, N) và q = N / p.
• Nếu không thì tìm chu kỳ r của hàm f(x) = a^x mod N, tức là f(x+r) = f(x).
• Nếu r lẻ, thì quay lại bước đầu tiên. Nếu a ^{r /2} ≡ −1 (mod N), thì quay lại bước đầu tiên. p = ƯCLN(a^r/2 + 1, N) và q = ƯCLN(a^r/2 - 1, N). 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. thumb|right|Biểu diễn trên mạch lượng tử của phần tính toán lượng tử của thuật toán Shor. 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>). Trạng thái của hệ 2 thanh ghi sau bước này là:

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à

iii) Áp dụng biến đổi Fourier vào hệ. Với $\backslash omega\; =\; e^\backslash frac\{2\; \backslash pi\; i\}\{Q\}$, 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ó:

Điều này dẫn đến trạng thái cuối:

Ta viết lại tổng trên dưới dạng:

Đâ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², từ đó suy ra có ít hơn Q giá trị phân biệt z = f(x). Lấy:

• $\backslash omega\; =\; e^\backslash frac\{2\; \backslash pi\; i\}\{Q\}$ là phương vị thứ _Q_^th
• r la chu kì của hàm f
• x₀ là giá trị nhỏ nhất của x thỏa mãn f(x) = z (ta có x₀ < r)
• b xác định theo x, mà khi chạy từ 0 tới $\backslash lfloor(Q\; -\; x\_0\; -\; 1)/r\backslash rfloor$ ta có .

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.

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