This problem is the problem I did not manage to solve in NUS Greyhats GreyCTF2022. Although I am pretty close to the solution, there is one trick that I missed that is crucial to this particular type of challenge. N = p * q c1 = (2 * p + 3 * q) ** e1 mod N c2 = (5 * p + 7 * q) ** e2 mod N We are given the above system of equations, and the goal is to solve for $p$ and $q$.

We are given the prime $p$ and the integers to find the quadratic residue in $p$. The exact values of the prime is given in this link Using Legendre Symbol and Euler’s criterion, a number $a$ can have three cases: $$ (\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} \equiv 1 \text{ if } a \text{ is a quadratic residue and } a \not\equiv 0 \mod p $$ $$ (\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} \equiv -1 \text{ if } a \text{ is a quadratic non-residue } \mod p $$

Implementation of the algorithm is in Sagemath: # Finding quadratic residue of a mod p from sage.rings.finite_rings.integer_mod import square_root_mod_prime a = <some a> p = <some p> print(square_root_mod_prime(Mod(a, p), p))