RSA

RSA는 널리 쓰이는 공개키 암호 알고리즘 가운데 하나다. 기본 동작은 다음과 같다.

서로 다른 두 홀수 소수 $P$와 $Q$를 골라 $N = PQ$를 계산한다. 이어서 오일러 피 함수 값 $\varphi(N) = (P - 1)(Q - 1)$을 구하고, $1 < E < \varphi(N)$이면서 $\gcd(\varphi(N), E) = 1$인 정수 $E$를 하나 고른다. 마지막으로 $\varphi(N)$을 법으로 하는 $E$의 곱셈 역원 $D$, 즉 $DE \equiv 1 \pmod{\varphi(N)}$을 만족하는 정수 $D$를 계산한다.

이렇게 두 정수 $N$과 $E$로 이루어진 공개키와, 두 정수 $N$과 $D$로 이루어진 비밀키를 얻는다.

$0 < M < N$인 메시지 $M$을 암호화할 때는 $C = M^E \bmod N$을 계산하고, 이 $C$가 암호문이다. 암호문을 복호화해 원래 메시지를 되찾을 때는 $M = C^D \bmod N$을 계산한다. 복호화에는 비밀키가 필요하고 공개키만으로는 부족하다. 위에서 쓴 $x \equiv 1 \pmod{y}$는 $x$를 $y$로 나눈 나머지가 1이라는 뜻이다.

이 문제에서는 RSA 암호를 깨야 한다. 공개키 $N$, $E$와 암호문 $C$만 보고 원래 메시지 $M$을 구하는 프로그램을 작성하시오.

첫째 줄에 세 정수 $N$, $E$, $C$가 공백으로 구분되어 주어진다. $15 \le N \le 10^9$, $1 \le E < N$, $1 \le C < N$이다.

$N$과 $E$는 위에서 설명한 RSA의 공개키이고, $C$는 이 공개키로 암호화한 메시지다. $N$은 서로 다른 두 홀수 소수의 곱이고, $\gcd(\varphi(N), E) = 1$이 항상 성립한다.

원래 메시지 $M$을 한 줄에 출력한다. $1 \le M < N$이다.