[Solved]: How hard is factoring a complex number?

Problem Detail: 

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?

Asked By : Mohammad Al-Turkistany

Answered By : Yuval Filmus

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14158

3.2K people like this

 Download Related Notes/Documents