P5451 [THUPC 2018] The Third Cryptography Homework

In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman proposed the RSA encryption algorithm. RSA is an asymmetric encryption algorithm, and its security depends on the difficulty of factoring very large integers. In other words, the harder it is to factor a very large integer, the more reliable RSA is. If someone finds a fast factoring algorithm, then the security of information encrypted with RSA will definitely drop a lot. The basic idea of RSA is as follows: - Generating the public key and private key 1. Randomly choose two different large primes $p$ and $q$, and compute $N=p\times q$. 2. By the property of Euler's totient function, compute $r=\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$. 3. Choose a positive integer $e$ less than $r$ such that $e$ and $r$ are coprime. Then compute the multiplicative inverse $d$ of $e$ modulo $r$, satisfying $ed\equiv 1 \pmod r$. 4. Destroy the records of $p$ and $q$. At this point, $(N,e)$ is the public key, and $(N,d)$ is the private key. - Message encryption: First, convert the message $m$ into an integer $n$ that is less than $N$ and coprime with $N$, in a format agreed upon by both parties. If the message is too long, it can be split into several parts (this is what we call block encryption). Then each part is encrypted using: $$ n^{e}\equiv c\pmod N $$ - Message decryption: Decrypt using the key $d$: $$ c^{d}\equiv n\pmod N $$

Now there are two users who, by coincidence, have the same modulus $N$ but different private keys. Let their public keys be $e_1$ and $e_2$, **and they are coprime**. The plaintext message is $m$, and the ciphertexts are: $$\begin{matrix}c_1=m^{e_1}\bmod N\\c_2=m^{e_2}\bmod N\end{matrix}$$ Now, an attacker has intercepted $c_1$, $c_2$, $e_1$, $e_2$, and $N$. Please help him recover the plaintext $m$.

The input contains multiple test cases. The first line contains an integer $T$ indicating the number of test cases, and it is guaranteed that $1\le T\le 10^4$ . Then each test case is described as follows: - One line contains five positive integers $c_1$, $c_2$, $e_1$, $e_2$, $N$. It is guaranteed that $2^{8}< N < 2^{63}$, $N$ has exactly two prime factors, and the other values are generated strictly according to the RSA algorithm described above.

For each test case, output $1$ line: - A non-negative integer $m$. Please make sure that $0\le m

### Copyright Information From the 2018 Tsinghua University Programming Contest and Intercollegiate Invitational (THUPC2018). Thanks to [Pony.ai](http://pony.ai/) for supporting this contest. Solutions and other resources can be found at . Translated by ChatGPT 5