# How hard is factoring a complex number?

Given complex number $C=a+ib$, I want to find two complex numbers $C_1=x+iy$ and $C_2=z+iw$ such that $C=C_1*C_2$ (a,b,x,y, z and w are all non zero integers). This problem is at least as hard as Integer factoring. Prime complex number has one as its only factor.

Does this problem reduce to integer factoring? Is it NP-hard?

• Such complex numbers are known as Gaussian integers. – Juho Sep 5 '13 at 22:30
• Not quite. Gaussian integers can have zero real or imaginary parts. For example, 2 and -4i are Gaussian integers. But OP is requiring the real and imaginary parts to be nonzero integers. – JeffE Sep 7 '13 at 17:06

If $C = \prod_i C_i$ is a prime factorization of $C$ then $N(C) = \prod_i N(C_i)$, where $N(\alpha + \beta i) = \alpha^2 + \beta^2$. Furthermore, $\pi$ is prime if either (i) $N(\pi) = 2$, (ii) $N(\pi) = 4a+1$ is prime, (iii) $N(\pi) = (4a+3)^2$ is the square of a prime. So factoring $C$ reduces to factoring $N(C)$.