인수분해(소인수분해)

자연수 N 을 소수의 곱으로 나타내는 문제다. 곱하기는 쉽지만 거꾸로 쪼개기는 어려워 보이며, N 의 자릿수에 대한 다항 시간 알고리즘은 (보통의 컴퓨터로는) 알려져 있지 않다. 결정 문제 판(「N 에 k 보다 작은 약수가 있는가」)은 NP 와 coNP 에 모두 속하므로 NP-완전은 아닐 것으로 여겨지고, NP-중간의 후보로 꼽힌다. 쇼어의 알고리즘은 양자 컴퓨터로 이를 다항 시간에 푼다. RSA 암호의 안전성이 이 문제의 어려움에 기대고 있다. 인수분해가 어렵다는 것은 증명된 사실이 아니다.