Modulo Multiplication Group - Square roots Let $p,q$ be two distinct prime numbers with $p,q\neq 2$, and let $n=pq$.
Suppose that we have an algorithm $A$ that takes in $b \in Z_n^*$ and returns


*

*If $b$ is a square number: return one of $b$'s square roots

*Otherwise, return nothing
$Z_n^*$ contains all numbers between $1$ (inclusive) and $n$ that are coprime with $n$.
How may one come up with an algorithm that computes $p$ and $q$ by calling algorithm $A$ a few times?
All ideas are appreciated. Thank you!

Lemma: If $\gcd(p,q)=1$, then $x^2\equiv b\pmod{pq}$ has a solution iff $x^2\equiv b\pmod{p}$ and $x^2\equiv b\pmod{q}$ have a common solution.
I have a feeling this might help you.
Edit: By trial and error, you could find the solutions of the equation mod p and mod q separately. And then check if either of the entries match.
