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

3more comments