Let $p,q$ be unknown primes and $n=pq$. Also let: $p\equiv 4 \mod 9$
$q\equiv 4 \mod 9$
Imagine I have an "oracle" that takes cube roots $\mod n$. Find a probabilistic algorithm to factor $n$.
I'm not sure where to start. I know the process for factoring $n$ given a square root $\mod n$ involves finding $\gcd{(\text{root y mod n}-y,n)}$.
As an example of an oracle that computes square roots, I might give it $50^2$ to hopefully factor $n=103\cdot 107$. It says the square root of $50$ is $\equiv 2625\mod 103\cdot 107$. So then it's computed: $\gcd(2625-50,103*107)=103$ and indeed $103$ divides $n$.
I'm assuming the process for cubes is similar, but I don't know what to do.