Should I expect that the Pollard rho method
1. x ← 2; y ← 2; d ← 1;
2. While d = 1:
1. x ← g(x)
2. y ← g(g(y))
3. d ← gcd(|x - y|, n)
3. If d = n, return failure.
4. Else, return d.
will work for Gaussian integers? With a minor change due to gcd?
In my blog Forth & math I use the method for single cell numbers and in works fine for 64-bit numbers. For integers I use the function $\;x^2+1$ and a complete factorization is delivered immediatly. Now I will try to define an adequate routine for Gaussian integers and I guess that the method reasonably often will deliver some non trivial factors, but how long would the cycles be before they repeat them selves? Do anyone know if this has been tried?
I have now implemented Pollard rho for Gaussian intergers on my blog and it seems to work fine.
However, $g(z)=z^2+1$ doesn't work for all Gaussian numbers, i.e. not for $4+3i$ but the function $g(z)=z^2-1$ is well tested and works. See my answer on stack overflow:
https://stackoverflow.com/questions/2269810/whats-a-nice-method-to-factor-gaussian-integers
Just with $\varrho$ over $\Bbb Z$, this depends on the (size of) the smallest prime factor. If the number has only (relatively) large factors, then you need many cycles. To give it a try, find the factorization of $$ 8529706411569586340464 + 101805471873703921229955\, i$$ Nothing special, just 2 prime factors that are not small.
What's the point? Would factorizing $z$ directly over $\Bbb Z[i]$ be better than factorizing $|z|^2=z\bar z$ over $\Bbb Z$? When you are computing $\gcd_{\Bbb Z[i]}$ you'll have divide $w$'s that are the size of about $z$; and to do that you'll extend with $\bar w$ and arrive at doing arithmetic with numbers of size $|z|^2$, just like when computing $\gcd_{\Bbb Z}$.
The advantage of factorizing over $\Bbb Z$ is that you can use all the nice factorization algorithms that already exists / are already implemented like ECM that's also very good at finding "small" factors.