Crack RSA

题目描述

Alan233's company deployed an RSA encryption system for all employees, but the security department, cutting corners, decided to let all employees share the same modulus $N$, assigning only different $(e_i, d_i)$ key pairs.

Employee P received their own key $(e, d)$ and somehow managed to hack into the company's system. While everyone was shocked, P explained nonchalantly: "I factored $N$."

Now, play the role of P and reproduce this attack. Given $T$ test cases, factor $N$ for each case and output $p$ and $q$.

Note that the basic RSA workflow is as follows:

• Pick two distinct large primes $p$ and $q$, and compute the modulus $N = p \times q$;
• Compute Euler's totient function $\varphi(N) = (p-1) \times (q-1)$;
• Choose $e$ coprime to $\varphi(N)$ as the public exponent;
• Compute $d$ satisfying $e \times d \equiv 1 \pmod{\varphi(N)}$ as the private exponent;
• $(N, e)$ is the public key and $(N, d)$ is the private key. Encryption computes $c = m^e \bmod N$, and decryption computes $m = c^d \bmod N$.

Formally, you're given $N,e,d$ satifying the above condition, you need to find out the value of $p$ and $q$.

输入格式

The first line contains an integer $T$ ($1\le T \le 10$). The next $T$ lines each contain three integers $N, e, d$($15\le N \lt 2^{256}$, $1 \lt e,d \lt \varphi(N)$, $N = p \times q$ ($p, q$ are primes), $e \times d \equiv 1 \pmod{\varphi(N)}$, and $3\le p \lt q \lt 2^{128}$).

输出格式

For each test case, output one line containing two integers $p, q$ such that $p \times q = N$ and $p \lt q$.

样例输入 #1

3
15 3 3
25777 3 16971
1005973 5 602381

样例输出 #1

3 5
149 173
997 1009