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ố^{[cần dẫn nguồn]}. 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 O((log N)²(log log N)(log log log N)) 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 ${\displaystyle {\sqrt[{k}]{N}}}$ có phải là số nguyên hay không, với mọi ${\displaystyle k\leq \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.

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à:

${\displaystyle Q^{-1/2}\sum _{x=0}^{Q-1}\left|x\right\rangle \left|0\right\rangle \,}$

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à

${\displaystyle Q^{-1/2}\sum _{x}\left|x,f(x)\right\rangle \,}$

iii) Áp dụng biến đổi Fourier vào hệ. Với ${\displaystyle \omega =e^{\frac {2\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ó: ${\displaystyle U_{QFT}\left|x\right\rangle =Q^{-{\frac {1}{2}}}\sum _{y}\omega ^{xy}\left|y\right\rangle .}$

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

${\displaystyle Q^{-1}\sum _{x}\sum _{y}\omega ^{xy}\left|y,f(x)\right\rangle .}$

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

${\displaystyle Q^{-1}\sum _{z}\sum _{y}\left|y,z\right\rangle \sum _{x:\,f(x)=z}\omega ^{xy}.}$

Đâ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:

• ${\displaystyle \omega =e^{\frac {2\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 ${\displaystyle \lfloor (Q-x_{0}-1)/r\rfloor }$ ta có ${\displaystyle x_{0}+rb<Q.}$.

${\displaystyle \omega ^{ry}}$ là một vecto đơn vị trong mặt phẳng phức (trong đó ${\displaystyle \omega }$ là căn đơn vị và r, y là các số nguyên dương), thì hệ số ${\displaystyle Q^{1}\left|y,z\right\rangle }$ trong trạng thái cuối là:

${\displaystyle \sum _{x:\,f(x)=z}\omega ^{xy}=\sum _{b}\omega ^{(x_{0}+rb)y}=\omega ^{x_{0}y}\sum _{b}\omega ^{rby}.}$

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.

${\displaystyle \left|Q^{-1}\sum _{x:\,f(x)=z}\omega ^{xy}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{(x_{0}+rb)y}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{bry}\right|^{2}.}$

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

Tham khảo

• https://vi.wikibooks.org/wiki/T%C3%ADnh_to%C3%A1n_l%C6%B0%E1%BB%A3ng_t%E1%BB%AD
• Nielsen, Michael A. & Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge University Press.
• Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007, ISBN 0-19-857049-X
• "Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). An alternate metaphor for the QFT was presented in one of the comments. Scott Aaronson suggests the following 12 references as further reading (out of "the 10¹⁰⁵⁰⁰⁰ quantum algorithm tutorials that are already on the web."):
• Shor, Peter W. (1997), “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM J. Comput., 26 (5): 1484–1509, arXiv:quant-ph/9508027v2, Bibcode:1999SIAMR..41..303S, doi:10.1137/S0036144598347011. Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
• Quantum Computing and Shor's Algorithm, Matthew Hayward's Quantum Algorithms Page, 2005-02-17, imsa.edu, LaTeX2HTML version of the original LaTeX document, also available as PDF or postscript document.
• Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, ngày 12 tháng 1 năm 1999, 9 page postscript document.
• Shor's Factoring Algorithm, Notes from Lecture 9 of Berkeley CS 294-2, dated 4 Oct 2004, 7 page postscript document.
• Chapter 6 Quantum Computation Lưu trữ 2020-04-30 tại Wayback Machine, 91 page postscript document, Caltech, Preskill, PH229.
• Quantum computation: a tutorial by Samuel L. Braunstein.
• The Quantum States of Shor's Algorithm, by Neal Young, Last modified: Tue May 21 11:47:38 1996.
• III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm, Lecture notes on Quantum computation, Cornell University, Physics 481-681, CS 483; Spring, 2006 by N. David Mermin. Last revised 2006-03-28, 30 page PDF document.
• Lavor, C.; Manssur, L. R. U.; Portugal, R. (2003). "Shor's Algorithm for Factoring Large Integers". arΧiv:quant-ph/0303175. 
• Lomonaco, Jr (2000). "Shor's Quantum Factoring Algorithm". arΧiv:quant-ph/0010034.  This paper is a written version of a one-hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
• Chapter 20 Quantum Computation, from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Comments welcome!, Sanjeev Arora and Boaz Barak, Princeton University.
• A Step Toward Quantum Computing: Entangling 10 Billion Particles Lưu trữ 2011-01-20 tại Wayback Machine, from "Discover Magazine", Dated ngày 19 tháng 1 năm 2011.
• Josef Gruska - Quantum Computing Challenges also in Mathematics unlimited: 2001 and beyond, Editors Björn Engquist, Wilfried Schmid, Springer, 2001, ISBN 978-3-540-66913-5