What algorithms are there for determining whether a Gaussian integer is prime?

Give a Gaussian integer $z\in{Z[i]}$, how can I determine if $z$ is prime? I imagine there exists an algorithm that maps primality in $Z[i]$ to primality in Z. And for the case when $z\in{Z}$ I think we can just check that $z$ is a prime in $Z$ and $z=3$ (mod 4).

-
– draks ... May 30 '12 at 21:43
Factoring just to determine primality seems expensive. – NoName May 30 '12 at 21:51
From en.wikipedia.org/wiki/Gaussian_integer : "A Gaussian integer a+bi is a Gaussian prime if and only if either: (i) one of a, b is zero and the other is a prime number of the form 4n+3 (with n a nonnegative integer) or its negative -(4n+3), or (ii) both are nonzero and a^2+b^2 is a prime number (which will not be of the form 4n+3)." – Steven Stadnicki May 30 '12 at 21:55
So the question was not about $z$ being non-decomposable over $\Bbb{Z}[i]$, unlike $-11+29i=(2+3i)(5+7i)$? – draks ... May 30 '12 at 22:02

If $z \in \mathbb{Z}[i]$ is truly complex, then the norm i.e. $\text{real}(z)^2+\text{imag}(z)^2$ should be a prime in $\mathbb{N}$. If $z \in \mathbb{Z}[i]$ is real or purely imaginary, then the real or imaginary part (whichever is non-zero) itself should be a prime of the form $3 \bmod 4$ in $\mathbb{Z}$.
@draks Briefly, because of the properties of the norm on the Gaussian integers - if we had $z=xy$ then $|z|^2 = |x|^2|y|^2$. If $|z|^2$ is a prime number, then you're done; either $|x|^2$ or $|y|^2$ must be $1$, and so one of $x$ and $y$ is a unit. Likewise, if $z=p$ is real and congruent to 3 mod 4, then because $|z|^2=p^2$, any factorization must take the form $z=x\bar{x}$ with $|x|^2=p$; but if $x=a+bi$, this says that $a^2+b^2 = p$, and primes of the form $4n+3$ aren't the sum of two squares. – Steven Stadnicki May 30 '12 at 22:37
Thanks    – draks ... May 30 '12 at 22:39