Đây là một trong những ứng dụng nổi tiếng và gây chấn động nhất của máy tính lượng tử: bẻ khóa hệ mật mã cổ điển như RSA, ECC, v.v. Mình sẽ giải thích rõ bằng một ví dụ cụ thể.
🚪 Vấn đề: Làm sao máy tính lượng tử mở khóa được RSA?
RSA – một trong những thuật toán mã hóa phổ biến nhất hiện nay – dựa vào việc phân tích một số lớn thành tích của hai số nguyên tố, một việc rất khó với máy tính cổ điển.
✅ Ví dụ: RSA đơn giản
Giả sử:
-
Khóa công khai gồm:
-
N=899 (gồm 2 số nguyên tố nhân lại)
-
e=3
-
-
Mật mã được gửi là C=800
👉 Để giải mã, cần biết khóa riêng tư:
-
Tính các số nguyên tố p,q sao cho N=p⋅q
-
Sau đó tìm d sao cho e⋅d≡1mod (p−1)(q−1)e \cdot d \equiv 1 \mod (p-1)(q-1)
Cách máy tính cổ điển làm:
-
Dò từng số để tìm 2 số nguyên tố nhân lại bằng 899
-
Tốn nhiều thời gian nếu N lớn (ví dụ: 2048 bit)
💥 Cách máy tính lượng tử làm – dùng Thuật toán Shor
Shor là thuật toán lượng tử có thể phân tích số nguyên thành thừa số nguyên tố rất nhanh.
🚀 Nguyên lý:
-
Máy lượng tử tạo chồng chập lượng tử (quantum superposition) cho tất cả các số x∈[1,N]
-
Áp dụng hàm lặp modulo f(x)=axmod N cho mỗi x – xử lý song song nhờ trạng thái lượng tử
-
Dùng biến đổi Fourier lượng tử (Quantum Fourier Transform) để tìm chu kỳ r của hàm f(x)
-
Nếu tìm được r, có thể tính:
gcd(ar/2−1,N)⇒p hoặc q\gcd(a^{r/2} - 1, N) \Rightarrow p \quad \text{hoặc} \quad q
📌 Ví dụ cực đơn giản:
Giả sử N=15, chọn a=7
-
71mod 15=7
-
72mod 15=47^2 \mod 15 = 4
-
73mod 15=137^3 \mod 15 = 13
-
74mod 15=17^4 \mod 15 = 1 ⇒ chu kỳ r=4
→ Tìm:
gcd(72−1,15)=gcd(49−1,15)=gcd(48,15)=3⇒p=3\gcd(7^{2} - 1, 15) = \gcd(49 - 1, 15) = \gcd(48, 15) = 3 \Rightarrow p = 3
Vậy: 15=3×5
✅ Tổng quát:
| Máy tính cổ điển | Máy tính lượng tử |
|---|---|
| Tính từng giá trị | Tính song song nhiều giá trị |
| Phân tích số lớn: rất chậm (bậc mũ) | Rất nhanh (đa thức) với Shor |
| RSA an toàn | RSA sẽ bị phá vỡ nếu lượng tử đủ mạnh |
🎯 Ứng dụng và nguy cơ thực tế:
-
Máy lượng tử với khoảng 4000+ qubit ổn định (logical qubit) có thể phá vỡ RSA-2048 → các tổ chức như Google, NSA, IBM đang chuẩn bị chuyển sang thuật toán hậu lượng tử (Post-Quantum Cryptography).
-
Hiện tại, máy lượng tử chưa đủ lớn để phá RSA thật sự, nhưng tương lai gần sẽ có.
