문제 설명
Rivest, Shamir, Adleman이 제시한 공개키 알고리즘은 두 개의 키를 사용한다. 여기서 키란 메시지를 열고 잠그는 상수를 의미한다. 일반적으로 많은 공개키 알고리즘의 공개키는 모두에게 알려져 있으며 메시지를 암호화하는데 쓰인다. 암호화된 메시지는 개인키를 가진 자만이 복호화하여 열어볼 수 있다. 공개키 알고리즘은 누구나 어떤 메시지를 암호화할 수 있지만, 그것을 해독하여 열람할 수 있는 사람은 개인키를 지닌 단 한사람만이 존재한다는 점에서 대칭키 알고리즘과 차이를 가진다.
다음은 A와 B가 보안이 보장되어 있지 않은 환경에서 서로 비밀 메시지를 주고 받고 싶다고 가정하였을 때, B가 A에게 메시지를 전달하기 위해 A의 공개키와 개인키를 생성하는 과정이다.
- p와 q라고 하는 두 개의 서로 다른 소수를 고른다. 소수는 1과 자기 자신으로만 나누어질 수 있다.
- 두 소수를 곱해서 암호화와 복호화를 위한 계수 N을 찾는다. 즉 N = p * q이다.
- 또다른 수 φ(N) = (p-1)(q-1)인 φ(N)을 계산한다.
- φ(N)보다 작고 φ(N)과 서로소인 정수 e를 찾는다.
- d × e를 φ(N)로 나누었을 때 나머지가 1이 될 수 있는 정수 d를 구한다.
- e와 N은 공개하고 φ(N)과 d는 비밀로 한다.
입력 설명
어떤 수 N이 입력된다.
\(2 \le N \le 2147483647\)
출력 설명
N이 두 소수의 곱으로 이루어져 있다면 두 소수를 오름차순으로 출력한다.(단, 두 소수는 같을 수 없다.)
만약 두 소수의 곱으로 이루어져 있지 않다면 "wrong number"를 출력한다.
입력 예시 Copy
6
출력 예시 Copy
2 3