Breaking the Asymmetric Encryption

This problem involves cracking a simplified version of an asymmetric encryption algorithm. The encryption works as follows:

1. Choose two distinct prime numbers \(p\) and \(q\).

2. Compute \(N = p \times q\) and \(r = (p-1)(q-1)\).

3. Select an integer \(e\) such that \(0 < e < r\) and \(\gcd(e, r)=1\).

4. Compute the integer \(d\) satisfying $$ ed \equiv 1 \pmod{r}. $$

5. The pair \((N, e)\) is the public key and \((N, d)\) is the private key.

To encrypt a message \(n\) (assume \(n < N\) and any message can be converted to an integer), the sender computes the ciphertext \(c\) using the public key as follows: $$ c \equiv n^e \pmod{N}. $$

To decrypt the ciphertext, one computes: $$ n \equiv c^d \pmod{N}. $$

Your task is to "crack" this encryption: given the public key \((N, e)\) and the ciphertext \(c\), recover the original message \(n\) by deriving the private key.

Note: You can assume that \(N\) is small enough to allow factorization by trial division.

inputFormat

The input consists of a single line with three positive integers separated by spaces:

• \(N\): the modulus (product of two primes).
• \(e\): the public exponent.
• \(c\): the ciphertext.

You may assume \(N\) is the product of two distinct prime numbers and \(n < N\).

outputFormat

Output the decrypted message \(n\) as a single integer.

sample

33 3 31

4