# Gaussian Prime Integers

in the ring $\mathbb{Z}[i]$ we have the units are $\{\pm 1\,\pm i\}$ and for $p\neq2$ , $p$ is prime if the $N(p)=a^2+b^2$ is prime and $p\equiv 1 \pmod4$

My Question is there any algorithm able to test given $p=a+ib$ is prime or not ?

## migrated from crypto.stackexchange.comDec 3 '16 at 23:58

This question came from our site for software developers, mathematicians and others interested in cryptography.

• @Ramez observe that for any complex number N(p) is an integer. Then apply all the algorithms you know in this case! – Robert NACIRI Dec 3 '16 at 14:07

Wait, there are three kinds of primes (up to units) in the Gaussian integers \begin{cases} 1 + i\\ \text{$q$, a prime integer with $q \equiv 3 \pmod{4}$}\\ \text{$a + i b$, where $r = a^{2} + b^{2}$ is a prime integer, $r \equiv 1 \pmod{4}$} \end{cases}
1. Check if $a + i b = 1 + i$.
2. If not, if $b = 0$ check whether $a$ is a prime integer, $a \equiv 3 \pmod{4}$.
3. If not, check whether $r = a^{2} + b^{2}$ is a prime integer, $r \equiv 1 \pmod{4}$.
Of course this is up to units, for instance $$1 + i, - 1 - i , i(1 + i) = -1 + i, (-i)(1 + i) = 1 - i$$ are all prime.