5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Such complex numbers are known as Gaussian integers. $\endgroup$
    – Juho
    Commented Sep 5, 2013 at 22:30
  • $\begingroup$ 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. $\endgroup$
    – JeffE
    Commented Sep 7, 2013 at 17:06

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Yuval. Could you give the details of the derivations of those statements? Are you taking into account the phase of complex numbers during factorization? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Sep 6, 2013 at 10:57
  • 2
    $\begingroup$ Look up any standard account of Gaussian integers. $\endgroup$
    – Yuval Filmus
    Commented Sep 6, 2013 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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