암호화는 NP 완전 문제에 기반하지 않는다

이 글에서는 암호화가 NP 완전 문제에 의존하지 않는 이유를 설명합니다. NP 완전 문제는 빠르게 푸는 것이 어렵지만, 암호화에는 평균적으로 어려운 문제, 즉 무작위로 선택된 인스턴스가 풀기 어려운 문제가 필요합니다. RSA는 대표적인 예시로, 큰 수의 소인수분해의 어려움에 의존하며, 평균적으로 어렵습니다. NP 완전 문제는 최악의 경우의 어려움만 보장하고 평균적인 어려움을 보장하지 않으므로 암호화에는 적합하지 않습니다.