====== 소수 증명 ======

주어진 [[자연수]]가 [[소수]]임을 증명하는 과정. 숫자가 커질 수록 이 증명 과정은 당연히 어려워지지만 놀랍게도 소수 증명 문제 자체는 [[다항시간]]에 풀 수 있다! ([[AKS]] 참고) 한편 [[소인수분해]]는 소수 증명보다 어려운 것으로 보이지만 확실하진 않다.

{{tag>수학}}