Finding factorization of $n = pq$ with an oracle that returns a random sq. root

Question

I'm trying to factor $n = pq$ where $p, q$ are large prime numbers with an oracle that returns a random sq. root.

My attempt after looking at this answer

I pick $a \in Z_n$ and run oracle on $a^2 \mod n$ to get $z$ s.t $z^2 \equiv a^2$

Now clearly, $n | z^2 - a^2$ which implies $n|z - a $ or $n| z + a$.

So then if $z$ is not a trivial sq. root (i.e $z \not\equiv \pm a)$ then I can simply get a factor by computing $gcd(z - a, n)$

I've 3 questions about this:

1) Can't we do it by computing $gcd(z + a, n)$ as well ?

2) Does $gcd(z - a, n)$ always return the smallest of $p, q$ ?

3) Moreover, can $z + a$ be anything? For example, I wanted to verify the method so I tried to factor $n = 14 = 7.2$ by computing sq. roots of $a^2 \equiv 4$ which are $12$ and $2$.

Now, for $z = 12$ and $a = 2, z + a = 14 \equiv 0 \mod 14$. Was that just a coincidence ?

Answer 1

Answers:

1. Yes. This will work equally well. This is because the oracle is equally likely to give you $n-z$ in place of $z$. And interchanging $z\leftrightarrow n-z$ will also intechange $\gcd(z-a,n)$ and $\gcd(z+a,n)$ because $(n-z)+a=n-(z-a)$, so $\gcd((n-z)+a,n)=\gcd(z-a,n)$.
2. No. $p$ and $q$ are equally likely to come out. There are four possibilities for $z$ (by Chinese Remainder Theorem). One of them gives $n$, one gives $1$, one gives $p$ and one gives $q$ as $\gcd(z-a,n)$. All depending whether both, neither or one but not the other of the congruences $z\equiv a\pmod p$ and $z\equiv a\pmod q$ is satisfied.
3. This was just a coincidence (unless the oracle doesn't really give a random square root).