# Given a deterministic oracle that calculates square roots modulo n, factor n

When $$n = pq$$ where $$p$$ and $$q$$ are primes, we can generate random numbers until we get $$a$$ and $$b$$ such that $$a^2 \equiv b^2 \pmod n$$. This implies $$n$$ has some common factor with $$a^2-b^2$$, and then we can use the Euclidean algorithm to find the gcd, which will be a factor of $$n$$.

However, I'm trying to figure out how to solve the problem when $$n$$ is an arbitrary number ($$n$$ being a product of two primes is not guaranteed). How could I generalize the above case to find a general solution?

• Just repeat the process until you've reduced all the factors to primes? – Squeamish Ossifrage Nov 15 '19 at 2:56
• Note: $n$ doesn't just have a common factor with $a^2 - b^2$; $n$ is a factor of $a^2 - b^2$, so $\gcd(n, a^2 - b^2)$ doesn't help. You need to go a step further to factor $n$. – Squeamish Ossifrage Nov 15 '19 at 2:58
• (Hint: Can you write $a^2 - b^2$ another way?) – Squeamish Ossifrage Nov 15 '19 at 3:05