③ 소인수분해

합성수를 소수들의 곱으로 나타내는 방법이다. 산술의 기본 정리에 따라, 모든 자연수는 소수들의 곱으로써 표현되는 방법이 유일하게 존재한다(곱의 순서를 바꾸는 것 제외).

하지만 소인수분해를 일의적으로 결정하는 공식은 현재까지 발견되지 않았다. 그래서 이를 기반으로 오늘날 공개키 암호시스템 중 하나인 RSA 암호체계가 만들어졌다.

1993년에 미국의 이론 컴퓨터 과학자 피터 쇼어는 양자 컴퓨터를 이용해 임의의 정수를 다항 시간 안에 소인수분해를 하는 ‘쇼어 알고리즘’을 발표했으나, 양자 컴퓨터가 그 정도 수준으로 실용화되기까지는 아직도 넘어야 할 산이 많은 상황이다.