전 세계 인터넷 보안의 근간을 이루는 RSA 암호를 정면으로 깨뜨리는 문제다.

RSA의 안전성은 큰 정수의 소인수분해가 어렵다는 가정에 전적으로 기대고 있다. 두 거대한 소수 \(p\), \(q\)의 곱 \(N = p \cdot q\)는 쉽게 만들 수 있지만, \(N\)만 보고 \(p\)와 \(q\)를 되찾는 것은 (고전 컴퓨터에서) 현실적으로 불가능하다고 믿어진다.

이 문제에서는 그러한 반소수(서로 다른 두 큰 소수의 곱) \(N\)이 주어진다. \(N\)을 이루는 두 소인수 \(p\)와 \(q\)를 찾아라.

$$ N = p \cdot q, \qquad p \le q, \qquad p, q \text{는 소수} $$

작은 \(N\)이라면 시험 나눗셈이나 Pollard rho로 충분하다. 그러나 채점 데이터의 \(N\)은 실제 RSA에서 쓰이는 2048비트(십진수 약 617자리) 규모이며, 현존하는 어떤 고전 알고리즘으로도 제한 시간 안에 인수분해할 수 없다. 이 문제를 통과한다는 것은 곧 RSA를 깨는 다항 시간 인수분해 알고리즘을 손에 넣었다는 뜻이다.

이 문제를 진짜로 푸는 코드를 제출하기 전에, 그 코드가 전 세계 은행·정부·메신저의 암호를 동시에 무력화한다는 사실을 떠올려 보라. 채점 버튼보다 책임감이 먼저다.

• \(6 \le N < 2^{2048}\)
• \(N = p \cdot q\)이며 \(p\), \(q\)는 서로 다른 소수이다.

첫째 줄에 분해할 정수 \(N\)이 주어진다. \(N\)은 서로 다른 두 소수의 곱이다.

한 줄에 두 소인수 \(p\)와 \(q\)를 공백으로 구분하여 \(p \le q\) 순서로 출력한다.

riseoj 작성

출처 Original