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.com Dec 3 '16 at 23:58

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

  • $\begingroup$ @Ramez observe that for any complex number N(p) is an integer. Then apply all the algorithms you know in this case! $\endgroup$ – 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}

So the algorithm is immediate, provided you can recognize prime integers efficiently.

  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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.