# Difficulty of factoring a Gaussian integer (compared to factoring its norm)

Given a Gaussian integer $G=a+ib$, with $gcd(a,b)=1$, a well-known strategy for factoring $G$ is to first compute its norm $N(G)=a^2+b^2$, factor the norm and finally recover the correct generator corresponding to each prime appearing in the factorization of the norm.

However, this approach neglects the fact that $G$ tells us a bit more than $N(G)$ since it gives a square root of $-1$ modulo $N(G)$ (in general, there is no efficient way to obtain this without factoring).

As a consequence, I am interested to know whether there is a dedicated algorithm for factoring large Gaussian integers that does not start by factoring its norm.

Since there was misunderstanding in the comments, here are some clarifications.

First, since $G=a+ib$ with $gcd(a,b)=1,$ $G$ cannot be divisible by an integer prime $p$. A direct consequence is that all prime factors of the norm of $G$ are congruent to $1$ modulo $4$ and $a/b$ is a square root of $-1$ modulo $N(G)$.

In other words, my question is: it is easier to factor the Gaussian integer $G$ than to factor the integer $N=N(G)$ without knowledge of $G$? An alternative formulation is: can we take advantage of the knowledge that $(a/b)^2\equiv -1 \pmod{N(G)}$ to factor $N(G)$ faster?

Note that I am not interested by the case where we have two elements $G$ and $G'$ with equal norms because then factoring is easy (assuming that we learn two square roots of $-1$ which are neither equal nor opposite).

• What is the correct generator corresponding to a prime? – Colin McLarty Aug 22 '13 at 19:22
• This is not a very precise question. Of course there are algorithms that don't start by factoring the norm. You can do trial division straight on the Gaussian integers. As there are no algorithms that perform better than general ones if the prime factors are all $3$ modulo $4$, one suspects that there are no factoring algorithms on the Gaussian integers that are better than the corresponding ones for the integers. – Felipe Voloch Aug 22 '13 at 19:23
• @FelipeVoloch The is precisely my question. Typically, if $N=pq$ with $p$ and $q$ large and congruent to $3$ modulo $4$, does it help to be given in addition a square root of $-1$ modulo $N$ (which using continued fraction gives $a+ib$ of norm $N$) ? – minar Aug 22 '13 at 19:33
• There is no square root of $-1$ modulo a product of primes congruent to $3$ modulo $4$. – Felipe Voloch Aug 22 '13 at 19:39
• @ColinMcLarty For simplicity, consider again $N=pq$ with $p$ and $q$ congruent to $3$ modulo $4$. Assume that $G=a+ib$ and $N(G)=N$. If $p$ factors as $p=(a_p+ib_p)(a_p-ib_p)$ you know that either $a_p+ib_p$ or $a_p-ib_p$ divides $G$. To test which one, multiply by the other. If you tried the right one, the result is divisible by $p$. – minar Aug 22 '13 at 19:39

If you are given the prime factorization of a Gaussian integer $G$, then taking the norms of the prime factors immediately gives you the prime(-power) factorization of $N(G)$, so factoring $G$ cannot be any faster than factoring $N(G)$.
• This does not answer the question. You prove that factoring $G$ cannot be faster than factoring $N(G)$ GIVEN a square root of $-1$ modulo $N(G)$. (If I only give you $N(G)$, there is no known way to find $G$ -- except by factoring first.) – minar Aug 23 '13 at 8:00