두 개의 서로 다른 소수의 곱인 정수 \(n\)이 주어진다. \(n\)을 이루는 두 소인수를 구하라.

이 문제에는 알려진 다항 시간 알고리즘이 존재하지 않는다. 큰 합성수의 소인수분해를 다항 시간에 해내는 방법이 발견된다면 RSA를 비롯한 현대 공개키 암호 체계가 모두 무너지게 된다. 즉, 이 문제는 "빠르게 푸는 법을 아무도 모르는" 문제이며, 어떤 영리한 테크닉을 숨겨 둔 것이 아니라 정말로 효율적인 해법이 존재하지 않는다.

히든 테스트의 \(n\)은 약 \(512\)비트 이상(각 소인수가 약 \(256\)비트 이상)이라, Pollard rho(\(\approx n^{1/4}=2^{128}\) 연산)나 ECM으로도 현실적인 시간 안에는 풀 수 없다.

\(4 \le n < 2^{1024}\). \(n\)은 항상 서로 다른 두 소수의 곱임이 보장된다.

한 줄에 서로 다른 두 소수의 곱인 정수 \(n\)이 주어진다.

\(n = p \cdot q\) (\(p < q\), 둘 다 소수)인 두 소수 \(p\), \(q\)를 오름차순으로 한 줄에 공백으로 구분하여 출력한다.

riseoj 작성

출처 Original