Vấn đề tính toán nào thường được liên kết với phân tích thành thừa số nguyên tố?
Vấn đề phân tích số nguyên là vấn đề tính toán xác định phân tích số nguyên tố của một số nguyên nhất định. Được gọi là vấn đề quyết định, đó là vấn đề quyết định xem đầu vào có yếu tố nhỏ hơn k hay không. Không có thuật toán phân tích số nguyên hiệu quả nào được biết đến và thực tế này tạo thành cơ sở của một số hệ thống mật mã hiện đại, chẳng hạn như thuật toán RSA. Vấn đề phân tích số nguyên nằm trong NP và trong co-NP (và thậm chí trong UP và co-UP). Nếu vấn đề là NP-hoàn chỉnh, hệ thống phân cấp thời gian đa thức sẽ sụp đổ đến cấp độ đầu tiên của nó (nghĩa là NP sẽ bằng co-NP). Thuật toán được biết đến nhiều nhất cho phân tích số nguyên là sàng trường số chung, mất thời gian O (e (64/9) 1/3 (n.log 2) 1/3 (log (n.log 2))2/3) để phân tích một số nguyên n-bit. Tuy nhiên, thuật toán lượng tử được biết đến nhiều nhất cho vấn đề này, thuật toán của Shor, chạy trong thời gian đa thức. Thật không may, thực tế này không nói nhiều về vấn đề nằm ở đâu đối với các lớp phức tạp không phải là lượng tử.
Bài toán phân tích thành thừa số nguyên