Description

The key generation process of an asymmetric encryption algorithm is as follows:

1. Choose two distinct prime numbers $p, q$.
2. Compute $N=p \times q$, $r=(p-1)(q-1)$.
3. Select an integer $e$ that is less than $r$ and coprime with $r$.
4. Compute an integer $d$ such that $ed≡1(mod r)$.
5. The ordered pair $(N,e)$ is called the public key, and the ordered pair $(N,d)$ is called the private key.

When encrypting a message $n$ (assume $n$ is an integer less than $N$, because any format of message can be converted to an integer), use the public key $(N,e)$ and compute

to obtain the ciphertext $c$.

To decrypt the ciphertext $c$, use the private key $(N,d)$ and compute

to obtain the original plaintext $n$. The proof of correctness is omitted.

Because ciphertext encrypted with the public key can only be decrypted with the corresponding private key, and not with the public key itself, this is called an asymmetric encryption algorithm. Typically, the public key is published by the message receiver, while the private key is kept by the receiver. In this way, anyone can encrypt messages using the public key, but only the receiver can decrypt them.

Now your task is to find a feasible method to crack this encryption algorithm: derive the private key from the public key and then use it to decrypt the ciphertext.

Input Format

The input contains a single line with three positive integers $e, N, c$ separated by spaces.

Output Format

Output a single line with two integers $d, n$ separated by a space.

3 187 45

107 12

Hint

• For $30\%$ of the testdata, $e, N, c \le 2^{20}$.
• For $100\%$ of the testdata, $e, N, c \le 2^{62}, c < N$.

Translated by ChatGPT 5