암호 해독자

미국 국가안보국(NSA)이 전 세계, 적어도 미국 안에서 오가는 이메일을 상당 부분 가로채 기록하고, 아마도 분석까지 하고 있다고 하자. 조직과 개인이 메시지의 프라이버시를 지키는 방법 하나가 암호화이고, 그중에서도 재미있는 아이디어가 공개키 암호다. 대강 이렇다. 키 하나를 공개하면 누구나 그 키를 보고 나에게 보낼 메시지를 암호화할 수 있다. 하지만 복호화하려면 다른 키가 필요하고, 그 키는 나만 알고 있다. 아이디어 자체보다 이것이 수학적으로 정말 가능하다는 사실을 보인 쪽이 훨씬 큰 기여였고, 그 답이 RSA 알고리즘이다.

방식은 이렇다. 소수 두 개 $p$, $q$를 고른다 (보통은 무작위로 고르지만 이 문제에서는 상관없다). 공개키는 $n = p \times q$와 작은 수 $e$로 이루어지고 누구나 볼 수 있다. 개인키는 $(d \times e) \bmod ((p-1)(q-1)) = 1$을 만족하는 수 $d \le (p-1)(q-1)$이고, 나만 알아야 한다. $p$와 $q$를 알면 이런 $d$는 쉽게 찾지만, 모르면 어렵다. $p$, $q$의 주인만 메시지를 복호화하는 이유가 여기에 있다.

암호화와 복호화는 이렇게 한다. 메시지를 수 $m$이라고 하자 (문자열은 그 비트를 하나의 수로 읽으면 언제든 수가 된다). 암호문은 $c = m^e \bmod n$이고, $n$과 $e$만 알면 계산된다. 받는 쪽은 $c^d \bmod n$을 계산해 원래 메시지를 되찾는다.

남의 키를 깨려면 $n$을 소인수분해해 $p$와 $q$를 복원하면 충분하다. $p$와 $q$가 충분히 크면 (수천 자리) 이 일은 어렵다고 여겨지지만 증명되지는 않았다. 반대로 너무 작으면 전수 조사만으로 RSA가 뚫린다. 이 문제에서 할 일이 바로 그것이다.

RSA의 R, S, A는 Rivest, Shamir, Adleman의 성에서 왔다.

첫 줄에 데이터 세트의 개수 $K$가 주어진다. 이어지는 $K$개의 줄에 데이터 세트가 하나씩 주어지고, 각 줄은 공백으로 구분된 정수 세 개 $n$, $e$, $c$로 이루어진다. $5 \le n \le 10^9$, $1 \le e \le 10000$, $1 \le c < n$이다. 즉 공격자는 공개키와 암호문을 모두 안다고 가정한다. 입력의 $n$은 언제나 정확히 두 소수의 곱이고, $e$는 위 조건을 만족하는 $d$가 존재하도록 주어진다.

각 데이터 세트마다 그 번호를 $x$라고 할 때 Data Set x:를 한 줄에 출력한다. 그다음 줄에 암호문 $c$를 복호화한 메시지 $m$을 출력하고, 그 뒤에 빈 줄을 하나 출력한다.