Shor liên kết phân tích số với tìm chu kỳ ra sao?

• Số lớn cần phân tích
• Bước tìm chu kỳ (đường lượn sóng)
• Hai thừa số

Bạn sẽ học được gì

• Nêu bài toán phân tích thừa số là gì và vì sao nó liên quan đến mật mã.
• Mô tả cách thuật toán Shor quy việc phân tích thừa số về tìm chu kỳ.
• Phân biệt điều thuật toán làm được trên lý thuyết với điều máy hiện nay đã làm.

Cần biết trước

Nên đọc trước bài Máy tính lượng tử xử lý thông tin như thế nào?. Các thuật ngữ khác được giải thích ngay trong bài.

Bài toán phân tích thừa số là gì, và vì sao quan trọng?

Đó là bài toán tìm các số nguyên tố nhân lại thành một số cho trước, và nó nằm ở lõi của nhiều giao thức mật mã. Theo Bách khoa toàn thư Triết học Stanford, sự quan tâm đến tính toán lượng tử ban đầu bắt nguồn từ P. W. Shor năm 1994. Ông cho thấy một thuật toán lượng tử dường như phân tích được số lớn thành số nguyên tố hiệu quả hơn nhiều so với mọi thuật toán cổ điển đã biết.

Nguồn Stanford nêu rằng phân tích thừa số nằm ở lõi của các giao thức mật mã dùng rộng rãi, như RSA. Chưa ai biết cách phân tích thừa số một số thành số nguyên tố theo thời gian đa thức bằng thuật toán cổ điển, và các thuật toán cổ điển tốt nhất hiện có chỉ là dưới mũ.

Vì vậy phát hiện rằng máy tính lượng tử có thể giải phân tích thừa số trong thời gian đa thức đã có tác động rất lớn.

• Số lớn cần phân tích
• Các thừa số cần tìm
• Đường cổ điển: dài và quanh co
• Đường quy về tìm chu kỳ: thẳng hơn

Shor biến phân tích thừa số thành tìm chu kỳ như thế nào?

Kết quả của Shor dựa trên phát hiện rằng bài toán phân tích thừa số quy về bài toán tìm chu kỳ của một hàm tuần hoàn nhất định. Nguồn Stanford mô tả đây là một lập luận số học khéo léo.

Các bước chính như sau.

1. Chọn một số ngẫu nhiên nhỏ hơn số cần phân tích và không có ước chung nào khác với số đó ngoài một.
2. Xét một hàm tuần hoàn xây từ lũy thừa của số vừa chọn, theo phép chia lấy dư cho số cần phân tích. Tìm chu kỳ của hàm này.
3. Biết chu kỳ, người ta phân tích được số ban đầu, với điều kiện chu kỳ chẵn và một điều kiện phụ. Nếu điều kiện không đạt, ta chọn một số khác và thử lại.
4. Các thừa số là ước chung lớn nhất của một số suy ra từ chu kỳ và số ban đầu, tìm được trong thời gian đa thức bằng thuật toán Euclid quen thuộc.

Phần máy lượng tử đảm nhiệm là bước 2. Theo nguồn Stanford, việc máy tính lượng tử giải hiệu quả bài toán này được gợi ý bởi thuật toán Simon, một thuật toán xét trường hợp hạn chế hơn của hàm tuần hoàn.

• Bước một: chọn số ngẫu nhiên
• Bước hai: hàm tuần hoàn
• Bước ba: chu kỳ (thước kẻ)
• Bước bốn: các thừa số

Shor có phá được mật mã ngay bây giờ không?

Không thể kết luận chỉ từ thuật toán. Phá khóa thực tế cần chứng minh máy đủ lớn và đủ tin cậy để chạy phép tính đó. Theo nguồn Stanford, việc chạy thuật toán Shor trên máy lượng tử quy mô lớn sẽ làm vô hiệu các hệ mật mã đang dùng rộng rãi, vốn dựa trên giả định rằng không có thuật toán hiệu quả cho phân tích thừa số.

Không nên dùng một ví dụ số nhỏ trong tài liệu để kết luận kỷ lục hiện tại. Điểm quan trọng ở đây là phân biệt thuật toán hiệu quả trên mô hình lý tưởng với phần cứng đủ lớn và đủ tin cậy để chạy nó trên khóa mật mã thực tế.

Về phía ứng phó, theo bản tin của NIST, NIST bắt đầu chọn và chuẩn hóa các thuật toán kháng lượng tử năm 2015. Các thuật toán đã chuẩn hóa dựa trên những bài toán toán học khác, khó với cả máy tính thông thường lẫn máy tính lượng tử.

• Máy quy mô lớn cần có (khung nét đứt)
• Máy nhỏ đã có
• Chuẩn kháng lượng tử (khiên)

Ví dụ trong đời sống

Hãy nghĩ tới một bánh xe quay đều có một vạch đánh dấu. Muốn biết sau bao lâu vạch lặp lại đúng vị trí cũ, ta chỉ cần tìm chu kỳ quay, không cần xét từng vòng. Shor làm việc tương tự với một hàm tuần hoàn: tìm chu kỳ rồi suy ra thừa số.

Đây là hình ảnh so sánh trực giác về khái niệm chu kỳ, không phải cách một máy lượng tử thực sự tính.

Hiểu lầm thường gặp

Thuật toán Shor không đọc mọi đáp án cùng lúc. Nó quy bài toán về tìm chu kỳ rồi dùng các bước toán học để suy ra thừa số.

Shor không có nghĩa mọi mật mã đều bị phá. Kết quả phân tích thừa số đe dọa các hệ dựa vào bài toán đó, như RSA; không thể suy từ nó rằng mọi thuật toán mật mã đều mất an toàn.

Máy lượng tử chưa được chứng minh vượt trội mọi mặt. Nguồn Stanford nói chưa có chứng minh cho sự vượt trội tổng quát.

Câu hỏi thường gặp

Thuật toán Shor làm gì?

Nó phân tích số lớn thành số nguyên tố bằng cách quy bài toán về tìm chu kỳ của một hàm tuần hoàn.

Vì sao Shor liên quan đến mật mã?

Phân tích thừa số nằm ở lõi của nhiều giao thức mật mã dùng rộng rãi, như RSA.

Shor đã phá được RSA chưa?

Chứng minh thuật toán chưa phải bằng chứng phá được khóa RSA thực tế. Điều kiện then chốt là chạy được phép tính đủ lớn và tin cậy; ví dụ số nhỏ không chứng minh điều đó.

Có giải pháp nào đối phó không?

NIST đã chuẩn hóa các thuật toán dựa trên bài toán toán học khó với cả máy thường lẫn máy lượng tử.

Tóm tắt

• Shor quy phân tích thừa số về tìm chu kỳ của một hàm tuần hoàn.
• Phần tìm chu kỳ là phần máy lượng tử được cho là làm hiệu quả.
• Phá mật mã cần máy quy mô lớn, và NIST đã chuẩn hóa thuật toán kháng lượng tử.