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