Factoring a large Gaussian integer $z_0 = a+bi$ into Gaussian primes may be done by first factoring the norm $N(z_0) = a^2 + b^2$ over the integers, and then considering the factors of each integer prime (see here).
However, this doubles the length of the integers involved in the problem. Naïvely, it would be faster to directly run the quadratic sieve algorithm over the Gaussian primes; i.e. evaluate the polynomial $P(z) = (z + w)^2 - z_0$ on a region around the origin, where $w$ is the closest lattice point to $\sqrt{z_0}$. We may compute roots of $P(z)$ modulo each Gaussian prime in our factor base, and sieve to locate smooth values of $P(z)$. The rest of the algorithm proceeds as usual, by searching for a linear dependence between the corresponding exponent vectors.
The two things I can see going wrong are:
- No fast algorithm to compute square roots modulo a Gaussian prime. However, this is a relatively small computation compared to the rest of the sieving process.
- Lower probability of smoothness when compared to the integer case. I don't know of any results on this, but I would be surprised if a Gaussian integer of norm $r$ is less likely to be smooth than a regular integer of size $r^2$.
I have implemented this algorithm (very unoptimized) and it works for small test cases ($a, b \sim 20$ digits). Are there any results on the runtime complexity of this algorithm, and why does nobody seem to use it?