- Round: 26 (2022/09)
- Category: Crypto
- Points: 75
- Solves: 39
Just RSA with an extra useless number that won't help you factoring it.
$\text{pqqp}=p^q+q^p$, so $\text{pqqp} = p \pmod{q}$ and $\text{pqqp} = q \pmod{p}$ by fermat little theorem. Then by definition, $\text{pqqp} = p+xq = q+yp$ for some integers $x,y$, and it has an obvious solution $x=y=1$. Therefore $pqqp=p+q$, and it is easy to factor $n$ from $p+q$ by solving it as a quadratic equation.