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).
What algorithms are there for determining whether a Gaussian integer is prime?
5
$\begingroup$
number-theory
algorithms
ring-theory
computer-science
-
0Also asked here: [whats-a-nice-method-to-factor-gaussian-integers@stackoverflow.com](http://stackoverflow.com/questions/2269810/whats-a-nice-method-to-factor-gaussian-integers) – 2012-05-30
-
0Factoring just to determine primality seems expensive. – 2012-05-30
-
0From http://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)." – 2012-05-30
-
0So the question was **not** about $z$ being non-decomposable over $\Bbb{Z}[i]$, unlike $-11+29i=(2+3i)(5+7i)$? – 2012-05-30
1 Answers
5
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}$.
-
0I recognize these are necessary conditions but are they also sufficient? – 2012-05-30
-
0@NoName Yes these are necessary and sufficient. – 2012-05-30
-
0and why are they sufficient? – 2012-05-30
-
3@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. – 2012-05-30